常用排序算法总结(冒泡、插入、选择、希尔、归并、快排、堆排序、基数排序)

针对常用的排序算法(冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序、堆排序、基数排序)的原理、稳定性、算法复杂度分别作了分析,并使用c++做了实现。

所有排序实现默认从小到大。

1. 冒泡排序 (Bubble Sort)

稳定排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

冒泡排序是最简单粗暴的排序方法之一。它的原理很简单,每次从左到右两两比较,把大的交换到后面,每次可以确保将前M个元素的最大值移动到最右边。

最好O(N),最坏O(N ^ 2),平均O(N ^ 2)

步骤

  1. 从左开始比较相邻的两个元素x和y,如果 x > y 就交换两者
  2. 执行比较和交换,直到到达数组的最后一个元素
  3. 重复执行1和2,直到执行n次,也就是n个最大元素都排到了最后

注意:

i从后向前走,注意i–,j从0至i之间的sort

1
2
3
4
5
6
7
8
9
10
11
void bubble_sort(vector<int>& nums){
int n = nums.size();
if(n<=1) return;
for(int i = n-1; i>=0; i--){
for(int j=0; j<i; j++){
if(nums[j]>nums[j+1])
swap(nums[j], nums[j+1]);
}
}
return;
}

其中swap代码可以换成下面两种:

1
2
3
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;

或者不借助tmp

1
2
3
nums[j] += nums[j + 1];
nums[j + 1] = num[j] - nums[j + 1];
nums[j] -= num[j + 1];

复杂度分析

由于我们要重复执行n次冒泡,每次冒泡要执行n次比较(实际是1到n的等差数列,也就是(a1 + an) * n / 2),也就是 O(n^2)。 空间复杂度是O(n)。

2. 插入排序(Insertion Sort)

稳定排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

插入排序的原理是从左到右,把选出的一个数和前面的数进行比较,找到最适合它的位置放入,使前面部分有序。

最好O(N),最坏O(N^2),平均O(N ^ 2)

步骤

  1. 从左开始,选出当前位置的数x,和它之前的数y比较,如果x < y则交换两者,否则跳出此次循环
  2. 对x之前的数都执行1步骤,直到前面的数字都有序
  3. 选择有序部分后一个数字,插入到前面有序部分,直到没有数字可选择
1
2
3
4
5
6
7
8
9
10
void InsertSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
swap(nums[j], nums[j - 1]);
}
}
return;
}

复杂度分析

因为要选择n次,而且插入时最坏要比较n次,所以时间复杂度同样是O(n^2)。空间复杂度是O(n)。

3. 选择排序(Selection Sort)

不稳定排序

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

最好,最差,平均都是O(N^2)

选择排序的原理是,每次都从乱序数组中找到最大(最小)值,放到当前乱序数组头部,最终使数组有序。

步骤

  1. 从左开始,选择后面元素中最小值,和最左元素交换
  2. 从当前已交换位置往后执行,直到最后一个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SelectionSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[i]) {
min = j;
}
}
swap(nums[min], nums[i]);
}
return;
}

复杂度分析

每次要找一遍最小值,最坏情况下找n次,这样的过程要执行n次,所以时间复杂度还是O(n^2)。空间复杂度是O(n)。

4. 希尔排序(Shell Sort)

不稳定排序

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

最好O(n logn logn),最坏 O(n ^ 2),平均O(n ^ 1 ~ 2)

希尔排序从名字上看不出来特点,因为它是以发明者命名的。它的另一个名字是“递减增量排序算法“。这个算法可以看作是插入排序的优化版,因为插入排序需要一位一位比较,然后放置到正确位置。为了提升比较的跨度,希尔排序将数组按照一定步长分成几个子数组进行排序,通过逐渐减短步长来完成最终排序。

例子

例如 [10, 80, 70, 100, 90, 30, 20] 如果我们按照一次减一半的步长来算, 这个数组第一次排序时以3为步长,子数组是:

10 80 70 90 30 20 100

这里其实按照列划分的4个子数组,排序后结果为

10 30 20 90 80 70 100

也就是 [10, 30 20 90 80 70 100]

然后再以1为步长生成子数组

10 30 20 ..

这个时候就是一纵列了,也就是说最后一定是以一个数组来排序的。

步骤

  1. 计算当前步长,按步长划分子数组
  2. 子数组内插入排序
  3. 步长除以2后继续12两步,直到步长最后变成1
1
2
3
4
5
6
7
8
9
10
11
12
void ShellSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return;
for (int gap = nums.size() >> 1; gap > 0; gap >>= 1) {
for (int i = gap; i < nums.size(); i++) {
for (int j = i; j >= gap && nums[j - gap] > nums[j]; j--) {
swap(nums[j - gap], nums[j]);
}
}
}
return;
}

复杂度分析

希尔排序的时间复杂度受步长的影响,具体分析在维基百科。

5. 归并排序(Merge Sort)

稳定性排序

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定性是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

最差最好平均都是O(nlogn)

归并排序是采用分治法(Divide and Conquer)的一个典型例子。这个排序的特点是把一个数组打散成小数组,然后再把小数组拼凑再排序,直到最终数组有序。

步骤

  1. 把当前数组分化成n个单位为1的子数组,然后两两比较合并成单位为2的n/2个子数组
  2. 继续进行这个过程,按照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
32
33
void Merge(vector<int>& nums, int start, int mid, int end) {
vector<int> left(nums.begin() + start, nums.begin() + mid + 1);
vector<int> right(nums.begin() + mid + 1, nums.begin() + end + 1);
int i = 0, j = 0, k = start;
while (i<left.size() && j<right.size()) {
if (left[i] <= right[j]) {
nums[k++] = left[i++];
}
else {
nums[k++] = right[j++];
}
}

while (i < left.size()) {
nums[k++] = left[i++];
}

while (j < right.size()) {
nums[k++] = right[j++];
}

return;
}

void MergeSort(vector<int>& nums, int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
MergeSort(nums, start, mid);
MergeSort(nums, mid + 1, end);
Merge(nums, start, mid, end);
}
return;
}

这个实现中加了一个temp,是和原数组一样大的一个空间,用来临时存放排序后的子数组的。

复杂度分析

在merge_array过程中,实际的操作是当前两个子数组的长度,即2m。又因为打散数组是二分的,最终循环执行数是logn。所以这个算法最终时间复杂度是O(nlogn),空间复杂度是O(n)。

6. 快速排序(Quick Sort)

不稳定排序

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

快速排序也是利用分治法实现的一个排序算法。快速排序和归并排序不同,它不是一半一半的分子数组,而是选择一个基准数,把比这个数小的挪到左边,把比这个数大的移到右边。然后不断对左右两部分也执行相同步骤,直到整个数组有序。

最好O(nlogn),平均O(nlogn),最差O(n ^ 2)

步骤

  1. 用一个基准数将数组分成两个子数组
  2. 将大于基准数的移到右边,小于的移到左边
  3. 递归的对子数组重复执行1,2,直到整个数组有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// start开始位置,end最后一位
int Patition(vector<int>& nums, int start, int end) {
int x = nums[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (nums[j] <= x) {
i++;
swap(nums[i], nums[j]);
}
}
swap(nums[++i], nums[end]);
return i;
}


void QuickSort(vector<int>& nums, int start, int end) {
if (start < end) {
int pos = Patition(nums, start, end);
QuickSort(nums, start, pos - 1);
QuickSort(nums, pos + 1, end);
}
return;
}

示例代码二:

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
int partition(vector<int>& nums, int i, int j){
if(i>=j)
return i;
int k=i+1;
for(; k<j; k++){
if(nums[k]>nums[j]){
swap(nums[k], nums[j]);
k--;
j--;
}
}
if(nums[k]<nums[i])
swap(nums[i], nums[k]);
return k;
}

void quick_sort(vector<int>& nums, int i, int j){
if(i>=j)
return;
int mid = partition(nums, i,j);
quick_sort(nums, i, mid-1);
quick_sort(nums, mid+1, j);
return;
}


int main(){
vector<int> nums = {4, 10, 4, 3, 8, 9};
quick_sort(nums, 0, 5);
for(auto num:nums)
cout<<num<<endl;
}

复杂度分析

快速排序也是一个不稳定排序,时间复杂度看维基百科。空间复杂度是O(n)。

7. 堆排序(Heap Sort)

堆排序经常用于求一个数组中最大k个元素时。因为堆实际上是一个完全二叉树,所以用它可以用一维数组来表示。因为最大堆的第一位总为当前堆中最大值,所以每次将最大值移除后,调整堆即可获得下一个最大值,通过一遍一遍执行这个过程就可以得到前k大元素,或者使堆有序。

时间复杂度,平均/最好/最坏均为O(nlogn)

在了解算法之前,首先了解在一维数组中节点的下标:

  • i节点的父节点 parent(i) = floor((i-1)/2)
  • i节点的左子节点 left(i) = 2i + 1
  • i节点的右子节点 right(i) = 2i + 2

步骤

  1. 构造最大堆(Build Max Heap):首先将当前元素放入最大堆下一个位置,然后将此元素依次和它的父节点比较,如果大于父节点就和父节点交换,直到比较到根节点。重复执行到最后一个元素。
  2. 最大堆调整(Max Heapify):调整最大堆即将根节点移除后重新整理堆。整理方法为将根节点和最后一个节点交换,然后把堆看做n-1长度,将当前根节点逐步移动到其应该在的位置。
  3. 堆排序(HeapSort):重复执行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
32
33
34
35
void MaxHeapify(vector<int>& nums, int begin, int end) {
int cur = begin;
int child = cur * 2 + 1;
while (child <= end) {
if (child + 1 < end && nums[child] < nums[child + 1]) {
child++;
}
if (nums[cur] < nums[child]) {
swap(nums[cur], nums[child]);
cur = child;
child = 2 * child + 1;
}
else {
break;
}
}
return;
}


void HeapSort(vector<int>& nums) {
int n = nums.size();
if (n <= 1) return;

for (int i = (n-2)/2; i >= 0; i--) { //最后节点n-1,然后((n-1)-1)/2;
MaxHeapify(nums, i, n - 1);
}

for (int i = n - 1; i > 0; i--) {
swap(nums[0], nums[i]);
MaxHeapify(nums, 0, i-1);
}

return;
}

复杂度分析

堆执行一次调整需要O(logn)的时间,在排序过程中需要遍历所有元素执行堆调整,所以最终时间复杂度是O(nlogn)。空间复杂度是O(n)。

8. 基数排序

稳定排序

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

堆排序、快排、归并代码实践

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<bitset>
using namespace std;


void merge(vector<int>&nums, int left, int mid, int right){
vector<int>l(nums.begin()+left, nums.begin()+mid+1);
vector<int>r(nums.begin()+mid+1, nums.begin()+right+1);
int i=0, j=0, k=left;
while(i<l.size()&&j<r.size()){
if(l[i]<=r[j]){
nums[k++] = l[i++];
}else{
nums[k++] = r[j++];
}
}
while(i<l.size()){
nums[k++] = l[i++];
}
while(j<r.size()){
nums[k++] = r[j++];
}

}

int partition(vector<int>& nums, int left, int right){
if(right==left)
return left;
int i = left-1;
int flag = nums[right];
int j=left;
for(;j<right; j++){
if(nums[j]<=flag){
swap(nums[++i], nums[j]);
}
}
swap(nums[++i], nums[right]);
return i;
}


void quick_sort(vector<int>& nums, int start, int end){
if(start<end){
int q = partition(nums, start, end);
quick_sort(nums, start, q-1);
quick_sort(nums, q+1, end);
}
}

void merge_sort(vector<int>& nums, int i, int j){
if(j>i){
int mid = i+(j-i)/2;
merge_sort(nums, i, mid);
merge_sort(nums, mid+1, j);
merge(nums, i, mid, j);
}
return;
}


void max_heapify(vector<int>& nums, int l, int r){
if(l==r)
return;
int parent = l;
int child = 2*l+1;
while(child<=r){
if(child+1<=r && nums[child+1]>nums[child])
child+=1;
if(nums[child]>nums[parent]){
swap(nums[child], nums[parent]);
parent = child;
child = parent*2+1;
}else{
break;
}
}
return;
}


void heap_sort(vector<int>& nums){
int n = nums.size();
if(n<=1) return;
for(int i=(n-1)/2; i>=0; i--){
max_heapify(nums, i, n-1);
}
for(int i=n-1; i>0; i--){
swap(nums[0], nums[i]);
max_heapify(nums, 0, i-1);
}
}

int main(){
vector<int> nums = {4, 10, 4, 3, 8, 9, 11, 1, 5, 21, 23, 2};
// quick_sort(nums, 0, nums.size()-1);
// merge_sort(nums, 0, nums.size()-1);
heap_sort(nums);
for(auto num:nums)
cout<<num<<endl;
}

参考资料:

  1. http://yansu.org/2015/09/07/sort-algorithms.html
  2. 《算法导论》
  3. http://yucc.me/p/176ecc84/
谢谢你,可爱的朋友。
显示 Gitment 评论