排序算法基本思想与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为数组中元素最大值与最小值的差。