排序算法
文章序
排序算法作为算法的入门，也是在日常开发中十分常用的，故在此整理出十大排序算法，方便自己和需要的朋友查阅
先定义交换函数
//不使用额外空间交换算法,不能自己跟自己换
function swap(array, i, j) {
if (i === j) {
return array;
}
let arr = array;
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
return arr;
}
//使用额外空间交换算法,可以自己跟自己换
function swap(array, i, j) {
let arr = array;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
1冒泡排序
原理：数组长度为 n，遍历 n - 1 趟，每趟从第 1 个元素向后两两比较，如果左边的元素大于右边的元素则将两个元素据交换，直到左边的元素为第 n - 1 个元素，交换完毕后，此时数组最右端的元素即为该数组中最大的元素。接着对该数组剩下的 n-1 个元素继续冒泡排序，直到整个数组有序排列
特性：时间复杂度：O(n^2)，空间复杂度：O(1) ，稳定排序 ，原地排序
方法：两层循环嵌套，外层共遍历 n - 1 趟，内层遍历从第 1 个元素到 n - 1 - i 个元素，进行两两比较交换
function bubbleSort(arr) {
let res = arr;
let n = arr.length;
for(let i = 0; i < n - 1; i++) {
for(let j = 0; j < n - 1 - i; j++) {
if(res[j] > res[j + 1]) {
res = swap(res, j, j + 1);
}
}
}
return res;
}
2选择排序
原理：遍历 n - 1 趟，每趟遍历找到剩余最小的元素放在前面，依次类推，直到数组有序排列
特性：时间复杂度：O(n^2) ，空间复杂度：O(1) ，非稳定排序，原地排序
方法：两层循环嵌套，外层共遍历 n - 1 趟，内层遍历从第 i 个元素开始，找到最小的元素和第 i 个元素交换
function selectionSort(arr) {
let res = arr;
let n = arr.length;
let minIndex = 0;
for(let i = 0; i < n - 1; i++) {
minIndex = i;
for(let j = i + 1; j < n; j++) {
if(res[j] < res[minIndex]) {
minIndex = j;
}
}
if(minIndex !== i) {
res = swap(res, i, minIndex);
}
}
return res;
}
3插入排序
原理：从第 1 个元素开始，将后面的元素与该元素比较，大则放在右边，小则放在左边，此时该两元素构成数组有序，剩余元素构成的数组无序，依次将剩余的元素向前面已有序数组中插入，直到整个数组有序
特性：时间复杂度：O(n^2)，空间复杂度：O(1) ，稳定排序 ，原地排序
方法：两层循环嵌套，外层共遍历 n - 1 趟代表插入 n - 1 个元素，内层遍历前面已有序数组直到找到合适的插入的元素的位置
function insertSort(arr) {
let res = arr;
let n = arr.length;
for (let i = 1; i < n; i++) {
for (let j = i - 1; j >= 0; j--) {
if (res[j] < res[j + 1]) {
break;
}
swap(res, j, j + 1);
}
}
return res;
}
4希尔排序
原理：定义增量(gap) h，将待排数组分割成为 h 个子数组分别进行插入排序，操作之后减小 h 的值，再次分别进行插入排序，直到 h = 1，则再进行最后一次插入排序，完成后整个数组排序完成
特性：时间复杂度：O(nlogn) ，空间复杂度：O(1) ，非稳定排序，原地排序
方法：三层遍历，最外层每次减少增量h的值，内两层做插入排序，注意间隔不再是 1 而是增量 h
function shellSort(arr) {
let res = arr;
let n = arr.length;
let h = parseInt(n / 2);
while (h >= 1) {
//进行插入排序
let i = 0;
let temp = 0;
while(temp < h) {
for (let j = i - h; j >= 0; j = j - h) {
if (res[j] < res[j + h]) {
break;
}
swap(res, j, j + h);
}
i = i + h;
if(i >= n) {
temp++;
i = temp;
}
}
h = parseInt(h / 2);
}
return res;
}
5快速排序
原理：选择一个元素，将比他大的都放到右侧，比它小的都放在左侧，此时数组分成两个数组，再次对两个数组进行快排，这样递归下去直到整个数组有序
特性：时间复杂度：O(nlogn)，空间复杂度：O(nlogn) ，非稳定排序，原地排序
方法：设指针 cur 指向第 1 个元素开始，指针 i 从 cur 指向元素向右走，指针 j 从最后一个元素向前走，j 先走，当 j 找到比 cur 小的元素停止，当 i 找到比 cur 大的元素停止，交换 i j指向的元素，直到i j相遇，交换此时cur 和 i 指向元素的位置，对此时指针左右两侧数组递归进行快排
function quickSort(arr) {
let n = arr.length;
handleSort(arr, 0, n - 1);
return arr;
}
const handleSort = (arr, start, end) => {
if (start >= end) {
return;
}
let cur = start,
i = start + 1,
j = end;
let mid = start;
while (true) {
while (j >= start && j > i) {
if (arr[j] < arr[cur]) {
break;
}
j--;
}
while (i <= end && i < j) {
if (arr[i] > arr[cur]) {
break;
}
i++;
}
if (i === j) {
if (arr[i] < arr[cur]) {
swap(arr, cur, i);
mid = i;
}
break;
}
swap(arr, i, j);
}
handleSort(arr, start, mid - 1);
handleSort(arr, mid + 1, end);
};
6归并排序
原理：将数组除2拆分，直到拆分到仅有一个元素的数组，此时该数组有序，将该数组与上一次拆分的另一个数组合并，此时本次拆分的数组有序，继续向上和上一次拆分的另一个数组合并，直到整个数组合并完毕，整个数组有序
特性：时间复杂度：O(nlogn)，空间复杂度：O(n)，稳定排序，非原地排序
方法：递归操作，先定义拆分函数mergeSort，再定义合并函数merge，拆分函数负责将入参数组除2拆分，并对拆分过的数组继续调用拆分函数，当两次拆分函数都调用完毕返回结果则调用合并函数
function mergeSort(arr) {
let n = arr.length;
if (n < 2) {
return arr;
}
let mid = parseInt(n / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, n);
let sortedLeft = mergeSort(left);
let sortedRight = mergeSort(right);
return merge(sortedLeft, sortedRight);
}
const merge = (left, right) => {
let res = [];
while (left.length > 0 && right.length > 0) {
if (left[0] < right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
if (left.length > 0) {
res = res.concat(left);
}
if (right.length > 0) {
res = res.concat(right);
}
return res;
};
7堆排序
原理：大顶堆为二叉树数结构，任意节点的值均大于左右子节点，数组可以构建一颗二叉树结构，将此数组调整为二叉树符合大顶堆的顺序，再依次交换第 0 个元素和第 n 个元素，并重新调整堆使之符合大顶堆定义，n依次递减直到n = 1，此时排序完成
特性：时间复杂度：O(nlogn)，空间复杂度：O(1)，非稳定排序，原地排序
方法：parseInt(n / 2)该元素为最后一个非叶子节点的数据，从这里开始遍历，构建大顶堆。大顶堆构建完成后将第 0 个元素和最后一个元素交换，此时剩下的堆不符合大顶堆定义，调整堆使符合大顶堆定义，再次交换第 0 个元素和此时最后一个元素，循环 n - 1 次结束获得有序数组
function heapSort(arr) {
let n = arr.length;
//从最后一个非叶子节点开始遍历，构建大顶堆
for (let i = parseInt(n / 2); i >= 0; i--) {
heapify(arr, i, n);
}
//大顶堆构建完毕，开始从最后一个元素开始交换
for (let j = arr.length - 1; j > 0; j--) {
n--;
swap(arr, 0, j);
heapify(arr, 0, n);
}
return arr;
}
function heapify(arr, i, n) {
//调整堆
let leftChild = 2 * i + 1;
let rightChild = 2 * i + 2;
let largest = i;
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest !== i) {
swap(arr, i, largest);
heapify(arr, largest, n);
}
}
8计数排序
原理：开辟新的数组 newArray，长度为 k，将待排数组内的元素值作为 newArray 的下标，将数组 newArray 从头遍历依次输出赋值给原数组即完成排序
特性：时间复杂度：O(n + m)，空间复杂度：O(n + m)，稳定排序，非原地排序
方法：
function countingSort(arr) {
let newArray = [];
let k = 0;
for (let i = 0; i < arr.length; i++) {
newArray[arr[i]] = arr[i];
}
for (let j = 0; j < newArray.length; j++) {
if (newArray[j]) {
arr[k] = newArray[j];
k++;
}
}
return arr;
}
9桶排序
原理：创建多个桶空间用来存放一定范围内的数据，每个桶内再排序，将数据按顺序从非空桶中取出，排序完成
特性：时间复杂度：O(n + m)，空间复杂度：O(n + m)，稳定排序，非原地排序
方法：创建一个数组，该数组内元素为数组表示不同的桶
function bucketSort(arr) {
let n = arr.length;
let max = arr[0];
let min = arr[0];
//找到最大最小值
arr.forEach(item => {
if (max < item) {
max = item;
} else if (min > item) {
min = item;
}
});
//设数组长度为桶长度，获取桶数量
let bucketCount = parseInt((max - min) / n);
let bucketList = new Array(bucketCount + 1);
for (let i = 0; i < bucketList.length; i++) {
bucketList[i] = [];
}
//将每一个数据放入到合适的桶
for (let j = 0; j < n; j++) {
let index = parseInt((arr[j] - min) / n);
bucketList[index].push(arr[j]);
}
//对每一个桶进行排序，这里选择计数排序
bucketList.forEach(bucket => {
countingSort(bucket);
});
for (let k = 0; k < bucketList.length; k++) {
if (k === 0) {
arr = [];
}
arr = arr.concat(bucketList[k]);
}
return arr;
}
10基数排序
原理：将数组按照从低位到高位的顺序排序，当每一趟都排序完成之后整个数组有序
特性：时间复杂度：O(nm)，空间复杂度：O(n + m)，稳定排序，非原地排序
方法：先找到最大的数并获取其位数 n，然后从个位开始向上遍历，共 n 次，每次遍历获取该数当前位的数并和桶里的数的当前位的数比较，没有当前位则补 0
function radixSort(arr) {
let max = arr[0];
//找到最大的数并获取其位数
arr.forEach(number => {
if (number > max) {
max = number;
}
});
const n = max.toString().length;
// let divide = Math.pow(10, n);
let divide = 1;
for (let i = 0; i < n; i++) {
let bucket = new Array(arr.length);
for (let j = 0; j < arr.length; j++) {
let tempNum = parseInt(arr[j] / divide);
while (tempNum >= 10) {
tempNum %= 10;
}
for (let k = 0; k < bucket.length; k++) {
if (bucket[k]) {
let tempBucketNum = parseInt(bucket[k] / divide);
while (tempBucketNum >= 10) {
tempBucketNum %= 10;
}
if (tempNum < tempBucketNum) {
bucket.splice(k, 0, arr[j]);
bucket.pop();
break;
}
} else {
bucket[k] = arr[j];
break;
}
}
}
divide *= 10;
arr = bucket;
}
return arr;
}
