各类排序算法对比

我记得网络上流传有一个演示在不同情况下9种排序算法表现的视频,还挺有趣的,今天从原理、时间复杂度、稳定性、适用场景方面分别分析这9种排序算法。

前言

在此之前大家可以看下这个浅谈算法的BBC先回顾下:

(bilibili地址,这里不引用bilibili因为bilibili比较模糊)

BBC讨论概况:

  • 通过一个小游戏讲述了算法在生活中的作用
  • 从1964年诞生的冒泡排序算法开始介绍排序的算法
  • 归并排序(拆分区域,分别合并有序的区域(由于有序对区域头分别对比即可),展示了只要数据一多归并排序对比冒泡排序的优势就展示出来了
  • 大概介绍了世界上有大约20种的排序算法
  • 最短路径问题: 通过实验,展示了蜜蜂在寻找最短路径上的天赋,不过蜜蜂并不是找到最短的路径,而是对于其而言接近最短路径,换言之是足够短的路径

I. 各类排序应用场景对比

世界上有大于20种的排序排序算法,比如网络上就有23种排序算法比较的视频。

再比如该圆盘排序对比给了很多有趣的排序,下面对其中提到效率对比:

  • Double Selection Sort
  • Gravity Sort
  • Counting Sort
  • Radix LSD Sort(Base 4)
  • Radix LSD In-Place Sort (Base 10)
  • Radix MSD Sort(Base 4)
  • Time Sort(mul 4) + Insertion Sort

不过今天我们主要谈到常见的9种排序。对于排序而言其效率无法进行纯粹的对比,因为其涉及的纬度众多,比如数据量,原本的混乱情况,读写速度、处理速度等都会对其影响。

不过我们今天就对于混乱情况借助下面这个很有意思的视频,对其效率进行排序下:

效率排名完全逆序乱序部分相同几乎有序
1快速排序(Quick)快速排序(Quick)快速排序(Quick)插入排序(Insertion)
2希尔排序(Shell)希尔排序(Shell)希尔排序(Shell)鸡尾酒排序(Cocktail)
3归并排序(Merge)归并排序(Merge)归并排序(Merge)快速排序(Quick)
4堆排序(Heap)堆排序(Heap)堆排序(Heap)希尔排序(Shell)
5梳排序(Comb)梳排序(Comb)梳排序(Comb)归并排序(Merge)
6选择排序(Selection)插入排序(Insertion)插入排序(Insertion)梳排序(Comb)
7插入排序(Insertion)选择排序(Selection)选择排序(Selection)堆排序(Heap)
8冒泡排序(Bubble)鸡尾酒排序(Cocktail)鸡尾酒排序(Cocktail)冒泡排序(Bubble)
9鸡尾酒排序(Cocktail)冒泡排序(Bubble)冒泡排序(Bubble)选择排序(Selection)
无序时间复杂度有序时间复杂度逆序时间复杂度
选择排序$O(n^2)$$O(n^2)$$O(n^2)$
插入排序$O(n^2)$$O(n)$$O(n^2)$
冒泡排序$O(n^2)$$O(n^2)$$O(n^2)$

II. 各类排序详细分析

1. 选择排序 - Selection sort

选择排序-维基

原理

选择排序为众多排序里面最简单暴力的方案,简而言之就是每次找到最小的放到前面: 遍历长度为n的整个数组,第i次遍历,找到最小的(或最大)与i所在值进行替换。

每次交换情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 6 1 8 2 4
↑ ↑
└─────┘
[1] 6 5 8 2 4
↑ ↑
└────────┘
[1, 2] 5 8 6 4
↑ ↑
└────────┘
[1, 2, 4] 8 6 5
↑ ↑
└─────┘
[1, 2, 4, 5] 6 8
[1, 2, 4, 5, 6] 8
[1, 2, 4, 5, 6, 8]

效率分析

  • 交换操作次数: [0, n-1] -> $O(n)$
  • 比较次数: (n-1) + (n-2) + … + 1 = $n\frac{(n-1)}{2} -> $O(n^2)$
  • 最好情况: 已经有序,交换0次
  • 最坏情况: 交换$n-1$次
  • 逆序交换: 交换$\frac{n}{2}$次
  • 稳定性: 不稳定排序(由于每次交换前后顺序就被破坏)
  • 时间复杂度: $O(n^2)$
  • 空间复杂度: $O(1)$

横向对比

  • 交换次数比冒泡排序少很多: 比冒泡排序快,由于交换所需CPU时间 > 比较所需CPU时间
  • 当记录占用字节数较多时,通常比插入排序执行速度快些。

2. 插入排序 - Insert sort

插入排序-维基, 在几乎排列好的队列中效率最高,因为在有序的队列中,其完全不用赋值,只需要进行$n-1$次比较即完成排序。

原理

插入排序的原理很想扑克牌抓牌,每次抓牌都是从桌面上的牌抓起插入已经排好序的手中的牌中: 往已经有序的数据序列中插入一个数,使得插入完成后依然有序。

每次交换情况(最坏也只需要$O(n)$次交换):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[5] 6 1 8 2 4
↑ │
└──┘
[5, 6] 1 8 2 4
↑ │
└───────┘
[1, 5, 6] 8 2 4
↑ │
└──┘
[1, 5, 6, 8] 2 4
↑ │
└──────────┘
[1, 2, 5, 6, 8] 4
↑ │
└───────┘
[1, 2, 4, 5, 6, 8]

效率分析

  • 稳定性: 稳定排序
  • 比较操作最好情况: 源数据有序,只需要$n-1$次
  • 比较操作最坏情况: 源数据逆序,需要$\frac{1}{2}n(n-1)$次
  • 赋值次数: $(比较操作次数) - (n-1)$ 因为$n-1$次循环中,每一次循环的比较都比赋值多一个,多在最后那次比较并不带来赋值
  • 时间复杂度: $O(n^2)$ (最坏: $O(n^2)$; 最优: $O(n)$)
  • 空间复杂度: 辅助空间$O(1)$

已有应用场景

  • 由于其时间复杂度的缘故,不适合用于数据量较大的数据(如量级大于千)
  • 在STL的sort算法和stdlib的qsort算法中被作为快速排序的补充,用于少量元素的排序(8个或以下)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void insertSort(int[] arr) {
int length = arr.length();
for (int i = 0; i < length - 1; i++) {
int j = i;
int tmp = arr[j + 1];
for(; tmp < arr[j] && j >= 0; j--) {
arr[j + 1] = arr[j]
}
// j = -1 or tmp >= arr[j]
if (i != j) {
arr[j + 1] = tmp;
}
}

3. 冒泡排序 – Bubble sort

冒泡排序-维基

原理

从后往前分别两两对比,遇到前一个比后一个小,就进行交换,这样每一轮下来就会有一个最小数被交换到前面,以此类推。
冒泡排序只要数据一多,排序效率将会大打折扣,

每次交换情况(需要$O(n^2)$次交换):

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
5 6 1 8 2 4
↑ ↑
└──┘
5 6 1 2 8 4
↑ ↑
└──┘
5 1 6 2 8 4
↑ ↑
└──┘
[1] 5 6 2 8 4
↑ ↑
└──┘
[1] 5 6 2 8 4
↑ ↑
└──┘
[1] 5 6 2 4 8
↑ ↑
└──┘
[1] 5 2 6 4 8
↑ ↑
└──┘
[1, 2] 5 6 4 8
↑ ↑
└──┘
[1, 2] 5 4 6 8
↑ ↑
└──┘
[1, 2, 4] 5 6 8
[1, 2, 4, 5] 6 8
[1, 2, 4, 5, 6] 8
[1, 2, 4, 5, 6, 8]

效率分析

  • 稳定性: 稳定排序(排序过程中,两两交换,相同元素前后顺序没有改变)
  • 比较操作最好情况: 源数据有序,只需要$n-1$次(移动0次)
  • 比较操作最坏情况: 源数据逆序,需要$\frac{1}{2}n(n-1)$次(移动$\frac{3}{2}n(n-1)$次)
  • 时间复杂度: $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
public static void bubbleSort(int[] arr){
boolean changed;
int len= arr.length;
do{
changed = false;
len-=1;
for (i = 0; i < len; i++) {
// move larger one to next each time.
if (arr[i] > arr[i+1]) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
changed=true;
}
}
} while(changed);
}

已有应用场景

鸡尾酒排序 – Cocktail Sort

将冒泡排序中,把走访数据的顺序反过来以提高效率。

[TODO]


Jacksgong wechat
欢迎关注Jacks Blog公众号,第一时间接收原创技术沉淀干货。