排序算法基本思想与JS实现
Posted by Mars . Modified at
各种排序算法基本思想描述与JS实现：冒泡、选择、插值（待补充）、希尔（待补充）、快速排序。
0. 总览
盗图一张。排序
1. 冒泡排序
从头开始，选出元素与其他元素逐一比较，并当场换位。
一次比较后，当前轮的极值一定会被放在边缘，然后排除这个极值开启下一轮比较，直到所有完成排序。
复杂度：
比较: O(n2)
交换: O(n2)
// 冒泡排序
let arr = [40,29,8,4,5,6,1,0,-1];
function bubble(arr){
let round = arr.length;
while(round >= 2){
for (let i = 0; i<round-1; i++){
if (arr[i]>arr[i+1]){
let temp = arr[i+1];
arr[i+1] = arr[i];
arr[i] = temp;
}
}
round--;
}
}
bubble(arr); // [-1, 0, 1, 4, 5, 6, 8, 29, 40]
2. 选择排序
逐一比较选出极值，依次放在一侧。直到所有的元素排序完毕。
复杂度：
比较: O(n2)
交换: O(n)
它与冒泡排序比较次数相同，但是不用每次都交换数据，相当于把冒泡法的多次交换汇总成一个，因此剩下了部分交换产生的时间复杂度。
let arr = [40,29,8,4,5,6,1,0,-1];
// 交换Arr中两个元素的函数
function _exchange(arr,a,b){
let temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
// 选择排序
function selectionSort(arr){
for (let j = 0; j < arr.length - 1; j++){
let min = j;
for (let i = j; i < arr.length; i++) {
if (arr[i] < arr[min]) {
min = i;
}
};
console.log(min);
_exchange(arr, j, min);
};
}
selectionSort(arr);
console.log(arr); //[-1, 0, 1, 4, 5, 6, 8, 29, 40]
3. 插入排序
4. 堆排序
5. 归并排序
先将数组二分，直到分成不可分割的单个元素数组，然后通过逐层向上合并成有序数组的方式，对整个数组排序。
特点： 稳定排序。
复杂度分析：
每一次拆分数组，数组的元素总数没有变化。一次拆分就对应着一次合并，每次合并都需要遍历拆分后数组的所有元素，因此单次合并时间复杂度为
O(N)。N个元素拆分到最小单元，拆分次数为
logN，也就是对应着logN次合并，因此总时间复杂度为O(NlogN)。
Time： O(NlogN) Space: O(N)
// 这里每次递归都创建了新数组，因此空间复杂度是O(NlogN)
function mergeSort(array) {
if(array.length === 1) return array;
function merge(arr1, arr2){
let p1 = 0, p2 = 0;
let res = [];
while(p1 < arr1.length || p2 < arr2.length){
if(p1 === arr1.length){
res.push(arr2[p2]);
p2++;
}
else if (p2 === arr2.length){
res.push(arr1[p1]);
p1++;
}
else {
if(arr1[p1] < arr2[p2]){
res.push(arr1[p1]);
p1++;
} else {
res.push(arr2[p2]);
p2++;
}
}
}
return res;
}
let mid = Math.floor(array.length/2);
let left = array.slice(0, mid);
let right = array.slice(mid);
let sortedLeft = mergeSort(left);
let sortedRight = mergeSort(right);
return merge(sortedLeft, sortedRight);
}
6. 快速排序
分而治之思想。就像二叉搜索树，一次选一个元素，把序列分为两半，左边一半都比元素小，右边一半都比元素大。
这样中间的元素位置就确定了。然后再用同样的算法，递归中间元素两边的序列，直到全部完成排序。
复杂度：
平均复杂度: O(n·log(n))
// 快速排序: 双指针法
//
// 首先是查找中间值（枢纽）并移动的函数：
// 1. 查找left到right的中点，然后对三者进行排序移动；
// 2. 把找到的中间点移动到倒数第二位置（right-1），因为已知最后的一个元素肯定大于它。这样方便后续的操作。
// 快速排序核心算法：
// 1. 对一个数组取中心点（枢纽），并使用findMedian函数排序并移动（移动后，最小值在left位置，最大值在right位置，枢纽也就是中值在right-1位置）；
// 2. 另设置两个指针，i从left向右，j从right-1位置向左依次查找。一旦发现i指向的元素大于枢纽值mid就停下来，j指向的元素小于枢纽值mid也停下来。
// 3. 交换i和j的值，然后继续2步骤；
// 4. 直到i<j，也就是二者交叉，停止搜索；
// 5. 把枢纽值(此时在right-1位置存放)与i元素进行对换，就实现了两侧分别小于和大于中间值的排序。
// 6. 此后，i-1作为左序列的right值，i+1作为右序列的left值，继续递归运算，left和right相交时，终止迭代，完成排序。
function quickSort(arr,left=0,right=arr.length-1){
function swap(i,j){
[arr[i], arr[j]] = [arr[j], arr[i]];
}
function findMid(left,right){
if(left > right) return ;
let mid = Math.floor((left+right)/2);
if(arr[mid] < arr[left]) swap(mid,left);
if(arr[right] < arr[mid]) swap(mid,right);
if(arr[mid] < arr[left]) swap(mid,left);
swap(mid,right-1);
return arr[right-1];
}
if(right - left <= 0) return;
if(right - left === 1 || right - left === 2){
findMid(left, right);
return;
}
let midVal = findMid(left,right);
let leftP = left, rightP = right-2;
while(leftP < rightP){
while(arr[leftP] < midVal) leftP++;
while(arr[rightP] >= midVal) rightP--;
if(leftP < rightP) swap(leftP, rightP);
}
swap(leftP,right-1);
quickSort(arr,left,leftP-1);
quickSort(arr,leftP+1,right);
}
quickSort(arr);
// [1, 4, 3, 0, 2, 6, 20, 10, 7, 70, 9]
// [1, 0, 2, 4, 3, 6, 20, 10, 7, 70, 9]
// [0, 1, 2, 4, 3, 6, 20, 10, 7, 70, 9]
// [0, 1, 2, 3, 4, 6, 20, 10, 7, 70, 9]
// [0, 1, 2, 3, 4, 6, 7, 9, 70, 10, 20]
// [0, 1, 2, 3, 4, 6, 7, 9, 10, 20, 70]
整个流程如下图所示。
7. 桶排序(Bin Sort)
7.1 桶排序原理
首先根据待排序元素的上下限，从左到右设置一系列桶容器。
将待排序元素按一定规则，放入多个桶容器中。每个桶容器单独排序，桶内可采用任何排序算法。
按桶的顺序依次取出元素，排好序即可。
7.2 复杂度分析
假设原始数组元素数目为n，桶数目为m。
那么，平均每个桶里面有n/m个元素。
如果使用快排，则每个桶的时间复杂度为O(n/m * log(n/m))，全部桶排好序的总复杂度为m * O(n/m * log(n/m)) = O(n * log(n/m))。
遍历整个数组的复杂度为O(n)，所以整体桶排序的复杂度为：
O(n + n * log(n/m))
最好情况：m=n，桶的数目与元素数目相同。此时为计数排序，复杂度为O(n)；
最坏情况：m=1，只有一个桶，此时退化为直接为原数组快速排序，复杂度为O(n*logn)。
8. 计数排序
在数组中的元素大小差别不大的时候可以使用，时间复杂度为线性。
先遍历数组，取元素最大值max和最小值min。
新建一个数组，长度为max-min+1。直接将每一个元素的值N减去min作为数组的索引(N-min)，放在这个数组中（重复则计数），然后从左到右遍历这个数组，依次按数目打印其中的元素即可。
Time： O(N+k)
Space: O(k)
n为原数组长度，k为数组中元素最大值与最小值的差。
