前言
排序是数据结构中很重要的一章，先介绍几个基本概念。
- 排序稳定性：多个具有相同的关键字的记录，若经过排序，这些记录的相对次
- 序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
一、插入排序
时间复杂度
最坏：-----------o(n^2)
最好：-----------o(n)
平均：-----------o(n^2)
空间复杂度
o(1)
稳定性：稳定
-『 插入排序 』：顾名思义就是把每一个数插入到有序数组中对应的位置。
就相当于你玩扑克牌的过程，抓来一张牌，就放在对应有序位置
直接插入排序：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
代码实现（升序）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void insertsort(int* a, int n){ for (int i = 0; i < n - 1; i++) { int x = a[end+1];//x为待排序的值 int end = i;//从end开始往前和x依次比较 while (end >= 0) { if (a[end] > x)//只要当前的值大于x继续往前找 { a[end+1] = a[end]; end--; } else { break;//跳出循环说明a[end] <= x } } a[end + 1] = x;//跳出循环说明a[end] <= x，需要把x插入到end前边 }} |
那么我们可以看到，越是接近有序的数组，插入排序的效率越高（有序时对于任何一个数只需要和前边的数比较一次）。
二、希尔排序
时间复杂度
o(n^（1.3—2）)
空间复杂度
o(1)
稳定性：稳定
『 希尔排序 』(shell's sort)是插入排序的一种又称“缩小增量排序”（diminishing increment sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 d.l.shell 于 1959 年提出而得名。
该方法实质上是一种『 分组插入 』方法,因为插入排序对于接近有序的数组排序效率非常高，那么希尔提出：
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
并且插入排序可以看成分组是1的希尔排序。动图如下：
因为插入排序可以看做gap==1的希尔排序，因此只需要改变插入排序中for循环的增量控制排序即可。
代码实现
|
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
|
void shellsort(int* a, int n){ //按gap分组进行预排序 int gap = n; while (gap>1) { //gap = gap / 2; gap = gap / 3 + 1;//这里分组选每次折半或者/3都可以 for (int j = 0; j < gap; j++)//gap个组 for (int i = j; i < n - gap; i+=gap)//每个组从j开始每个增量gap { int end = i; int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = x; } }} |
关于希尔排序时间复杂度证明比较复杂，取决于gap怎么取，如果按照knuth提出的/3，来取是o(n^（1.25）- 1.6*o(n^1.25).
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
三、选择排序
时间复杂度
最坏：-----------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
|
void selectsort(int* a, int n){ int begin = 0; int end = n - 1; int mini = begin;//记录最小值下标 while (begin<end) { for (int i = begin; i < end; i++) { if (a[i] < a[mini]) { mini = i;//更新最小值下标 } } swap(&a[mini],&a[begin]);//把最小值放到左边 ++begin;//左边对应起始位置++ }} |
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。
四、堆排序
时间复杂度
最坏：-----------o(n * logn)
最坏：-----------o(n * logn)
平均：-----------o(n*logn)
空间复杂度
o(1)
堆排序(heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
具体可见另一篇文章堆排序和topk问题
动图：
代码实现
|
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
|
void swap(int* px,int* py){ int t = (*px); (*px) = (*py); (*py)= t ;}void adjustdown(int* a, int n, int parent){ int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child + 1] > a[child]) { child++; } if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } }}void heapsort(int* a, int n){ for (int i = (n - 1 - 1) / 2; i >= 0; i--) { adjustdown(a, n, i); } for (int i = n - 1; i > 0; i--) { swap(&a[0], &a[i]); adjustdown(a, i, 0); }} |
五、冒泡排序
时间复杂度
最坏：-----------o(n^2)
最好：-----------o(n)
平均：-----------o(n^2)
空间复杂度
o(1)
『 冒泡排序 』是大家最熟悉的也是最容易理解的排序,如下图：
『 冒泡排序基本思想 』就是每一次将相邻的数据进行『 两两比较 』，选出最大的依次比较送到右边，那么最右边就是最大值，而左边留下的自然就是小的（排升序）
-『 冒泡排序 』需要两层循环
『 内层循环 』表示一次冒泡，也就是两两比较先选出最大的放到最右边，同时注意每一次冒泡选出最大元素，那么两两比较次数-1（下一次不用比较选好的最右边）
『 外层循环 』控制的是冒泡的次数（假设数组n 个元素）也就是n-1次冒泡选出n-1个最大的元素
代码实现
初版代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//初版：void swap(int* px, int* py){ int t = (*px); *px = (*py); (*py) = t;}void bubblesort(int* a, int n){ for (int i = 0; i < n-1; i++)//外层循环 { for (int j = 0; j < n-1-i; j++) { if(a[j]>a[j+1]) swap(&a[j],& a[j + 1]);//交换 flag = 1; } }} |
时间复杂度分析：每一次比较次数是n-1,n-2,n-3***1.因此是n(n-1)/2
但是这种写法还是有缺陷，时间复杂度永远是o(n^2） ， 对于一个已经排好序的数组来说，还是需要n^2的复杂度，但对于有序的数组，每一次冒泡都不会进行交换因为有序，因此如果只要任何一次冒泡中没有数据交换就证明数组有序了。时间复杂度最好也可以达到0(n)。
代码优化如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
//优化：void bubblesort(int* a, int n){ for (int i = 0; i < n-1; i++) { int flag = 0; for (int j = 0; j < n-1-i; j++) { if(a[j]>a[j+1]) swap(&a[j],& a[j + 1]); flag = 1; } if (flag == 0) break; }} |
六、快排排序
时间复杂度
最坏：-----------o(n^2)
最好：-----------o(logn)
平均：-----------o(logn)
空间复杂度
o(logn)
『 快速排序 』是hoare于1962年提出的一种二叉树结构的交换排序方法，其『 基本思想 』为：任取待排序元素序列中的某元素作为『 基准值 』，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。如图：
代码实现
递归写法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 假设按照升序对a数组中[left, right)区间中的元素进行排序void quicksort(int* a, int left, int right) { if(right >= left ) return;//递归截止条件 // 按照基准值对a数组的 [left, right]区间中的元素进行划分 int keyi= partion(a, left, right); // 划分成功后以keyi为边界形成了左右两部分 [left, keyi-1] 和 [keyi+1, right] // 递归排[left, keyi-1] quicksort(a, left, keyi-1); // 递归排[keyi+1, right] quicksort(a, keyi+1, right);} |
递归框架写完了接下来就差partion函数的实现也就是快排的灵魂，去每一次找基准值。那么一共有三种写法如下：
hoare版本
1.首先就是要找基准值，这里你可以选最左边或最右边的值（图中是6）
2.两个指针指向头（这里选左为基准值，头指针指向第二个）和尾，基准值选左，则右指针先走，反之左指针先走。
3.左指针找到比基准值大的停下，右指针找比基准值小的停下，交换左右指针指向值
4.重复2.3动作，直到左右指针相遇，交换左指针值和基准值
左值为基准，右指针先走找比6小的：
左值为基准，右指针先走找比6小的：
交换：
最终效果：相遇交换左指针和基准值，保证了6的左边都比6小，右边比6大。
并且除此之外，由于我们看到这种算法类似于二叉树的思想排好中间再排左右子树，因此我要保证选取的随机值尽量位与中位数。所以我们采取三数取中的方法。（选取最左值最右最中间的数的中位数）效率是可以提升5%到10%的。
|
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
|
//三数取中int getmidindex(int* a, int left, int right){ //int mid = (left + right) / 2; //int mid = left + (right - left) / 2; int mid = left + ((right - left)>>1); if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right]) { return left; } else { return right; } } else//a[left] > a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right]) { return left; } else { return right; } }}int partion(int* a, int left,int right){ int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int keyi = left; while (left < right) { while (left < right && a[right] >= a[keyi]) { right--; } while (left < right && a[left] <= a[keyi]) { left++; } swap(&a[left], &a[right]); }swap(&a[left], &a[keyi]); return left;} |
挖坑法
挖坑法就是对hoare版本的一种变形，过程如下：
初始如下：先保存基准值，基准值形成一个坑位！
左为基准，右指针先走，找到小的送到坑位，那么此刻右指针形成了新的坑位
左指针出动，找到大的继续送到坑位，左指针形成了新的坑位
指针相遇，把6写入。也保证左边比6小，右边比6大。代码如下：
|
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
|
//挖坑法int partion2(int* a, int left, int right){ int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int key = a[left]; int pivot = left; while (left < right) { //右边先找小 while (left< right && a[right] >= key) { --right; } a[pivot] = a[right]; pivot = right; while (left < right && a[left] <= key) { ++left; } a[pivot] = a[left]; pivot = left; } a[pivot] = key; return pivot;} |
前后指针版本
顾名思义，使用两个指针，这里选取左为基准值为例，两个指针从左开始出发一个cur,一个prev。
要求：
cur指针先走，一旦找到比基准值小的就停下，++prev,并交换。
cur指针一直到头为止，最后交换prev指向值和基准值
1和2都比6小cur走一步停一步，prev++并交换，指向相等。
cur越过7和9去找小的3，此时停下，prev++指向7交换。（我们注意到prev和cur不等时prev永远是去找大的，cur是找小的，因此交换就做到把cur指向的小的往前扔，大的往后仍，）
整个过程如上，代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//前后指针法int partion3(int* a, int left, int right){ int mini = getmidindex(a, left, right); swap(&a[mini], &a[left]); int prev = left, cur = left+1; int keyi = left; while (cur<=right) { if (a[cur] < a[keyi] && ++prev !=cur) { swap(&a[prev], &a[cur]); } cur++; } swap(&a[prev], &a[keyi]); return prev;} |
小结
递归版本三种方法如上，但是递归毕竟有缺陷，就是需要不断开辟栈帧，当数据量超过10w以上时就会有栈溢出的风险。
并且递归类似二叉树的结构越往下递归调用越多，栈帧翻倍开辟，因此我们还可以去优化一下，就是当递归到左右区间比较小时，我们去控制剩下的排序用别的排序来代替它。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//优化：void quicksort(int* a, int left, int right){ if (left >= right) return; if (right - left + 1 < 10) { //小区间优化 insertsort(a + left , right - left + 1); } else { int keyi = partion3(a, left, right); quicksort(a, left, keyi - 1); quicksort(a, keyi + 1, right); } } |
非递归：
非递归版本就是改变了快排的框架，用一个栈和循环来代替递归实现。依次将左右下标入栈出栈（出栈之前排序）来模拟递归。
|
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
|
void quicksortnonr(int* a, int left, int right){ stack st;//定义一个栈 stackinit(&st);//初始化 stackpush(&st, left);//左下标入栈 stackpush(&st, right);//右下标入栈 while (stackempty(&st)!=0) { int end = stacktop(&st);//获取栈顶元素即后入栈的右下标 stackpop(&st);//出栈 int begin = stacktop(&st);//获取栈顶元素即先入栈的左下标 stackpop(&st);//出栈 int keyi = partion3(a, begin, end); if (keyi + 1 < end)//相当于递归左半部分 { stackpush(&st, keyi + 1); stackpush(&st, right); } if (keyi - 1 > begin)//相当于递归右半部分 { stackpush(&st, keyi - 1); stackpush(&st, begin); } }} |
七、归并排序
时间复杂度
最坏：-----------o(nlogn)
最好：-----------o(nlogn)
平均：-----------o(nlogn)
空间复杂度
o(n)
稳定性：稳定
基本思想：
归并排序（merge-sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（divide andconquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 动图演示：
归并的思想就是把先假设数组分成两个有序，对其进行筛选排序，如上图：
但是问题来了我们怎么保证数组是有序的？因此就要求我们从小区间开始对数组归并排序，对于上图中的数据，先对开始3和3归并，小的先进入到tmp数组，因此前两个就是有序，再对，5和6归并，5,6有序后，在归并3，3，5，6……以此类推
代码实现
递归写法
框架：
|
1
2
3
4
5
6
7
8
9
10
11
|
void mergesort(int* a,int n){ int* tmp = (int*)malloc(sizeof(int) * n);//开辟n个大小数组 if (tmp == null) { exit(-1); } _mergesort(a, 0, n - 1, tmp);//进行归并操作 free(tmp); tmp = null;} |
归并排序：
运用递归先不断缩小偏序区间，在递归层层退出时一遍退出，一边对不断回大的区间归并排序：
|
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
|
void _mergesort(int* a, int left, int right,int* tmp){ if (left >= right) { return;//递归截止条件left >= right区间中数的个数<=0个 } int mid = left + (right - left) / 2;//取中 _mergesort(a, left, mid, tmp);//对左区间递归 _mergesort(a, mid+1, right, tmp);//对右区间递归 int begin1 = left, end1 = mid;//左区间 int begin2 = mid+1, end2 = right;//右区间 int i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1 ) { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } for (size_t i = left; i <= right; i++) { a[i] = tmp[i];//把排好序[left,right]的tmp赋值给原数组 }} |
非递归
非递归的不同就是需要手动控制区间大小，也就是不断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
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
|
void mergesortnonr(int* a, int n){ int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == null) { exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { //[i][i+gap-1] [i+gap][i+2*gap-1] int begin1 = i, end1 = i + gap-1; int begin2 = i + gap, end2 = i + 2 * gap - 1; int index = i; if (end1 >= n || begin2 >= n) { break; } if (end2 >= n) { end2 = n - 1; } while (begin1<=end1 && begin2<=end2) { if (a[begin1] <= a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } //控制越界问题三种情况 if (end1 >= n) { end1 = n - 1; } if (end1 >= n) { end1 = n - 1; } if (end1 >= n) { end1 = n - 1; } for (int j = i; j <= end2; j++) { a[j] = tmp[j]; } } gap *= 2; } free(tmp); tmp = null;} |
八、计数排序
时间复杂度
最坏：-----------o(max(n,范围))
最好：-----------o(max(n,范围))
平均：-----------o(max(n,范围))
空间复杂度
o(范围)
稳定性：不稳定
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
动图如下：
类似桶排序的思想，如上图，先开辟数组统计数组中某一个数出现的次数，比如2出现1次，3出现两次，那么我们直接按顺序读入开辟的数组，在原数组写1一个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
26
27
28
29
30
|
void countsort(int* a, int n){ int max=a[0], min= a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); memset(count, 0, sizeof(int)*range); for (int i = 0; i < n; i++) { count[a[i] - min]++; } int j = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[j++] = i + min; } }} |
计数排序的特性总结：
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
九、各种排序总结比较
1. 复杂度总结
2. 性质分类
以上就是c语言 八大排序算法的过程图解及实现代码的详细内容，更多关于c语言八大排序算法的资料请关注服务器之家其它相关文章！
原文链接：https://blog.csdn.net/weixin_51484780/article/details/121628023
