前言
面试的时候，面试官问到了排序算法的问题，自感觉这方面还是不够熟练。所以写一篇blog总结一下。
冒泡排序
这是最简单也是复杂度最高的排序算法了，这是一种稳定的排序算法，因为它最终相同元素的相对顺序没有发生改变。
复杂度
- 时间复杂度：
- 平均情况：$O(n^{2})$
- 最好情况： $O(n)$
- 最坏情况：$O(n^2)$
- 空间复杂度： $O(1)$
原理
从第一个元素开始，遇到小的就交换位置。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
functionbubbleSort(arr){
var len=arr.length;
for(var i=0;i<len;i++){
for(var j=0;j<len-1-i;j++){
if(arr[j]>arr[j+1]){
var temp = arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}
function bubbleSortOther(arr){
var len=arr.length;
for(var i=0;i<len;i++){
for(var j=i+1;j<len;j++){
if(arr[i]>arr[j]){
var temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(bubbleSort(arr));
|
直接插入排序
这种排序是一种稳定的排序。属于插入排序比冒泡排序稍快。
复杂度
- 时间复杂度：
- 平均情况：$O(n^{2})$
- 最好情况： $O(n)$
- 最坏情况：$O(n^2)$
- 空间复杂度： $O(1)$
原理
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
假设元素组为[20,60,10,40,30,70]
在此排序中，数组会被划分为两种，“有序数组块”和“无序数组块”，
第一遍的时候从”无序数组块“中提取一个数20作为有序数组块。
第二遍的时候从”无序数组块“中提取一个数60有序的放到”有序数组块中“，也就是20，60。
第三遍的时候同理，不同的是发现10比有序数组的值都小，因此20，60位置后移，腾出一个位置让10插入。
然后按照这种规律就可以全部插入完毕。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
function insertSort(arr){
for(var i=1;i<arr.length;i++){
var x=arr[i];
for(var j=i-1;arr[j]>x;j--){
arr[j+1]=arr[j];
}
if(arr[j+1]!=x){
arr[j+1]=x;
}
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(insertSort(arr));
|
下面是i每次递增之后的数组变化：
4321->3421->2341->1234
4231->2431->2341->1234
希尔排序
也是插入排序的一种，也叫递减增量排序算法，是直接插入排序的一种进化版。它是一种不稳定的排序算法。
复杂度
- 时间复杂度：
- 平均情况：$O(n^{1.3})$
- 最好情况： $O(n)$
- 最坏情况：$O(n^2)$
- 空间复杂度： $O(1)$
原理
1、先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。
3、取第二个增量 d2<d1 重复上述的分组和排序，
4、直至所取的增量dt=1(dt<dt-l<…<d2<d1) ，即所有记录放在同一组中进行直接插入排序为止。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function shellSort(arr){
var gap=Math.floor(arr.length/2);
while(gap>0){
for(var i=gap;i<arr.length;i++){
temp=arr[i];
for(var j=i;j>=gap&&arr[j-gap]>temp;j-=gap){
arr[j]=arr[j-gap];
}
arr[j]=temp;
}
gap=Math.floor(gap/2);
}
return arr;
}
var arr = [2,3,6,4,2,1,90,100,20,5];
console.log(shellSort(arr));
|
归并排序
这是一种稳定的排序算法。速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列.属于分治思想，递归归并。
复杂度
- 时间复杂度：
- 平均情况：$O(nlog_2{n})$
- 最好情况： $O(nlog_2{n})$
- 最坏情况：$O(nlog_2{n})$
- 空间复杂度： $O(n)$
原理
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
1、把长度为n的输入序列分成两个长度为n/2的子序列;
2、对这两个子序列继续分为m/2的子序列，一直分下去；
3、将两个排序好的子序列合并成一个最终的排序序列。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
function merge(left, right) {
var re = [];
while(left.length > 0 && right.length > 0) {
left[0] < right[0] ? re.push(left.shift()) : re.push(right.shift());
}
return re.concat(left).concat(right);
}
function mergeSort(arr) {
if(arr.length == 1){
return arr;
}
var mid = Math.floor(arr.length / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(mergeSort(arr));
|
快速排序
速度最快。和归并排序不同的是，归并排序是先分为两组再继续排，而快速排序是边分边排。
复杂度
- 时间复杂度：
- 平均情况：$O(nlog_2{n})$
- 最好情况： $O(nlog_2{n})$
- 最坏情况：$O(n^2)$
- 空间复杂度： $O(nlog_2{n})$
原理
1、在数据集之中，选择一个元素作为”基准”（pivot）；
2、所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边；
3、对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
function quickSort(arr){
if(arr.length<=1){
return arr;
}
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];
var left=[];
var right=[];
for(var i=0;i<arr.length;i++){
arr[i] <= pivot ? left.push(arr[i]) : right.push(arr[i]);
}
return quickSort(left).concat([pivot],quickSort(right));
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(quickSort(arr));
|
直接选择排序
它是冒泡排序的衍生算法，但是一种不稳定的排序算法
复杂度
- 时间复杂度：
- 平均情况：$O(n^2)$
- 最好情况： $O(n^2)$
- 最坏情况：$O(n^2)$
- 空间复杂度： $O(1)$
原理
在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后剩下的数当中找出最小的与第二个位置的数交换，如此循环直到倒数第二个数和最后一个数为止。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
function selectSort(arr){
length = arr.length;
for (var i = 0; i < length; i++){
var _min = arr[i];
var k = i;
for (var j = i + 1; j < length; j++){
if (_min > arr[j]){
_min = arr[j];
k = j;
}
}
arr[k] = arr[i];
arr[i] = _min;
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(selectSort(arr));
|
奇偶排序
奇数和偶数序列交替比较，是一种稳定的排序算法。
复杂度
- 时间复杂度：
- 平均情况：$O(nlog_2{n})$
- 最好情况： $O(nlog_2{n})$
- 最坏情况：$O(n)$
- 空间复杂度： $O(1)$
原理
奇偶排序的核心是，以奇数列为基准和以偶数列为基准对整个数组进行排序。而排序的元素只有两个，基准元素和其右侧相邻的一个元素。
1、选取所有奇数列的元素与其右侧相邻的元素进行比较，将较小的元素排序在前面；
2、选取所有偶数列的元素与其右侧相邻的元素进行比较，将较小的元素排序在前面；
3、重复前面两步，直到所有序列有序为止。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| function oddEvenSort(arr){
var swaped=true;
var k=0;
while(swaped){
if(k>0){
swaped=false;
}
for(var i=k;i<arr.length-1;i+=2){
if(arr[i]>arr[i+1]){
arr[i]=[ arr[i+1], arr[i+1]=arr[i] ][0];
swaped=true;
}
}
k=[1,0][k];
}
return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(oddEvenSort(arr));
|
使用sort进行排序
原理
sort() 方法用于对数组的元素进行排序，并返回数组。默认排序顺序是根据字符串UniCode码。因为排序是按照字符串UniCode码的顺序进行排序的，所以首先应该把数组元素都转化成字符串（如有必要），以便进行比较。
在不同引擎中对js的sort方法解析可能存在差异。在v8引擎中对sort方法提供了2中排序算法：插入排序以及快速排序。
在v8/array.js的源码中注释有对于length<=22的短数组，插入排序会更有效。在使用的时候，判断当Array.length<=10的使用插入排序，其他情况会使用快速排序，但是针对长度在10到1000的数组和大于1000的会选择不同的基准值。
具体情况请看：V8sort源码
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| var a = [1,4,3,2,5];
var b = ['a','c','b','D','A','C']
b.sort()
a.sort((e1,e2)=>{return e1-e2})
var ObjA = [{name:'assign',id:2},{name:'cycle',id:3},{name:'box',id:1}]
ObjA.sort(function(e1,e2){
var s1 = e1['name'].slice(0,1).charCodeAt();
var s2 = e2['name'].slice(0,1).charCodeAt();
return s1-s2;
})
ObjA.sort(function(e1,e2){
var v1 = e1['id'];
var v2 = e2['id'];
return v1-v2;
})
|