前端内参
搜索文档…
贰.1.1 十大排序算法
先看一张图表总结个中排序算法对比(点击可看大图)。

01.冒泡排序

1
((arr) => {
2
for(let i=0;i<arr.length;i++){
3
for(let j=i+1;j<arr.length;j++){
4
if(arr[j]<arr[i]){//从左往右升序排列
5
//交换位置
6
let tmp=arr[i];
7
arr[i]=arr[j];
8
arr[j] = tmp;
9
}
10
}
11
}
12
console.log(arr);
13
})([1, 5, 4, 2, 9, 7, 8]);//>>[1,2,4,5,7,8,9]
Copied!
因为嵌套两个for循环,所以冒泡排序的时间复杂度为
O(N2)O(N^2)

02.选择排序

假设数组A里面有N个项,选择排序是这样的:数组A第i个项记作
AiA_i
,第(i+1)~(N-1)项中的最小(最大的情况也是相似的逻辑)值记作
AmA_m
,然后比较它俩大小,如果
AmA_m
小于
AiA_i
,交换位置……直到把整个数组处理一遍。代码如下:
1
((arr) => {
2
let N = arr.length;
3
for(let i=0;i<N;i++){
4
let min=arr[i+1],minIndex=i+1;//记录第(i+1)~(N-1)项中的最小值以及对应的索引
5
for(let j=i+1;j<N;j++){
6
if(arr[j]<min){//从左往右升序排列
7
minIndex=j;
8
min = arr[j];
9
}
10
}
11
if (arr[minIndex] < arr[i]) {
12
//交换位置
13
let tmp = arr[i];
14
arr[i] = arr[minIndex];
15
arr[minIndex] = tmp;
16
}
17
}
18
console.log(arr);
19
})([1, 5, 4, 2, 9, 7, 8]);//>>[1,2,4,5,7,8,9]
Copied!
可以看出选择排序也是一外一内两个for循环,因此时间复杂度也是
O(N2)O(N^2)
。但是选择排序与冒泡排序差别地方在于:
  • 选择排序的位置交换是在第二个for循环之外,第一个for循环之内,因此选择排序交换位置最多N次,而冒泡排序最多可能
    N2N^2
    次。所以大多数情况下,选择排序比冒泡排序效率好一些。

03.插入排序

插入排序我们打扑克时给手中牌排序的思路一样,刚开始左手上一堆乱序的牌,我们把牌往手的右边挪一挪,把手的左边空出一点位置来,然后在右手乱牌中抽一张出来,插入到左边,再抽一张出来,插入到左边……每次插入都插入到左边合适的位置,时刻保持左边的牌是有序的,直到右边的牌抽完,则排序完毕。
代码实现如下:
1
//todo
Copied!
从代码里我们可以看出,如果找到了合适的位置,就不会再进行比较了,就好比右手里抽出的一张牌本身就比我左手里的牌都小,那么我只需要直接放在左手靠边位置就行了,不用一张一张去移动牌腾出位置插入到中间。
所以说,最好情况的时间复杂度是
O(N)O(N)
,最坏情况的时间复杂度是
O(N2)O(N^2)
,然而时间复杂度这个指标看的是最坏的情况,而不是最好的情况,所以插入排序的时间复杂度也是
O(N2)O(N^2)

04.堆排序

堆的特性:
  • 必须是完全二叉树;
  • 任一结点的值是其子树所有结点的最大值或最小值。 最大值时,称为“最大堆”,也称大顶堆; 最小值时,称为“最小堆”,也称小顶堆。
堆排序主要用到最大堆/最小堆的删除操作,也即根节点已经是最大/小的值,排序的话,只需要把根结点拿(删)掉,放入有序的新数组里,然后用下沉算法处理剩余的结点以便组成新的最大堆/最小堆……如此循环。
所谓下沉算法,拿最小堆来举例说(最大堆同理),就是把完全二叉树根结点R和该树第二层左右子结点的值比较,如果大,结点就互换位置(“下沉”),以此逐层递归,直到处理完整棵树,此时,根节点值最小。
1
((arr) => {
2
var result = [];
3
4
buildMinHeap(arr);
5
6
for (let i = 0, length = arr.length; i < length; i++) {
7
//将堆(完全二叉树)的根结点拿走,放入result数组,此时result是已排序好的。
8
result.push(arr[0]);
9
10
//将堆(完全二叉树)的根结点和最末尾的结点交换
11
swap(0, length-result.length);
12
//然后下沉,重排树,让根节点是最小的。注意【数组范围】是length-result.length
13
sink(arr, 0, length - result.length);
14
}
15
16
//根据给定的数组建一个最小堆
17
function buildMinHeap(arr) {
18
let length = arr.length;
19
let currentIndex;//当前要处理的下沉结点对应的数组索引
20
//请注意,currentIndex为什么是从 Math.floor((length - 2) / 2) 开始?
21
//读者可以画个草稿图归纳一下。
22
//这会让算法的循环次数由N次变为logN,这正是堆排序更高效的关键所在。
23
for (currentIndex = Math.floor((length - 2) / 2); currentIndex >= 0; currentIndex--) {
24
console.log("正在处理的下沉结点索引为:"+currentIndex);
25
sink(arr, currentIndex, length);
26
}
27
}
28
29
/**
30
* 下沉算法
31
* @param arr 数组
32
* @param currentIndex 要处理的结点的索引,该结点有子结点
33
* @param length 数组范围
34
*/
35
function sink(arr, currentIndex, length) {
36
37
let minIndex=currentIndex;//较小值的索引,默认为currentIndex
38
39
let leftChildIndex = 2*currentIndex+1;//完全二叉树 左子结点索引
40
let rightChildIndex = 2*currentIndex+2;//完全二叉树 右子结点索引
41
42
//左侧下沉
43
if(leftChildIndex < length && arr[leftChildIndex] < arr[minIndex])
44
minIndex = leftChildIndex;
45
46
//右侧下沉
47
if (rightChildIndex < length && arr[rightChildIndex] < arr[minIndex])
48
minIndex = rightChildIndex;
49
50
if(minIndex!=currentIndex){
51
swap(minIndex,currentIndex);
52
//递归,继续下沉,时间复杂度为O(N)
53
sink(arr,minIndex,length);
54
}
55
}
56
57
//交换位置
58
function swap(x, y) {
59
let tmp = arr[x];
60
arr[x] = arr[y];
61
arr[y] = tmp;
62
}
63
64
console.log(result);
65
66
})([1, 5, 4, 2, 9, 7, 8]);//>> [1, 2, 4, 5, 7, 8, 9]
Copied!
草稿图可以这么画,然后归纳、设计代码,更方便理解。
堆排序的时间复杂度是
O(NlogN)O(NlogN)

05.归并排序

//todo

06.快速排序

快速排序其实是分治法,将待排序数组里的项和基准数对比,比基准数大的放在一边,小的放另一边,然后再对左右两边的子数组重复使用这个思路,直到整个数组排序完毕。
1
((arr) => {
2
/**
3
* @param left 数组的最左侧项的索引
4
* @param right 数组的最右侧项的索引
5
*/
6
function quicksort(left, right) {
7
let i/*左指针索引*/, j/*右指针索引*/, temp/*基准数*/;
8
if (left > right)
9
return;
10
temp = arr[left];//取数组第一个项为基准数
11
i = left;
12
j = right;
13
while (i != j) { //若左右两个指针没碰头
14
while (arr[j] >= temp && i < j)//顺序很重要,要先从右边开始找,直到找到比temp小的为止
15
j--;
16
while (arr[i] <= temp && i < j)//再找左边的,直到找到比temp大的数为止
17
i++;
18
if (i < j)//交换这两个数在数组中的位置,让小的在左边,大的在右边
19
{
20
let t = arr[i];
21
arr[i] = arr[j];
22
arr[j] = t;
23
}
24
}
25
//然后将基准数与小的数换位,将小的数放在最左边,基准数放中间
26
arr[left] = arr[i];
27
arr[i] = temp;
28
29
quicksort(left, i - 1);//递归。继续处理左边的,这里是一个递归的过程
30
quicksort(i + 1, right);//递归。继续处理右边的 ,这里是一个递归的过程
31
}
32
33
quicksort(0, arr.length - 1);
34
console.log(arr);
35
})([1, 5, 4, 2, 9, 7, 8]);//>> [1, 2, 4, 5, 7, 8, 9]
Copied!
时间复杂度最好的情况是
O(NlogN)O(NlogN)
,最差的情况是
O(N2)O(N^2)
。算法分析:
  • 当分区选取的基准元素为待排序元素中的最大或最小值时,为最差的情况,时间复杂度和直接插入排序的一样,移动次数达到最大值
    Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) 此时时间复杂为
    O(N2)O(N^2)
  • 当分区选取的基准元素为待排序元素中的"中值",为最好的情况,时间复杂度为
    O(NlogN)O(NlogN)

07.希尔排序

//todo

08.计数排序

//todo

09.桶排序

//todo

10.基数排序

//todo
最近更新 1yr ago