排序算法总结（多图）
2019-03-24 本文已影响234人
凯睿看世界
1. 概述
| 算法名称 | 复杂度 | 实现关键 |
|---|---|---|
| 冒泡排序 | O(n^2) | （无序区，有序区）。从无序区通过交换找出最大元素放到有序区前端。 |
| 选择排序 | O(n^2) | （有序区，无序区）。在无序区里选择一个最小的元素跟在有序区的后面。 |
| 插入排序 | O(n^2) | （有序区，无序区）。把无序区的第一个元素插入到有序区的合适的位置。 |
| 希尔排序 | nlog^2(n) | 每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1(插入)。 |
| 快速排序 | nlog(n) | （小数，枢纽元，大数）。 |
| 堆排序 | nlog(n) | |
| 桶排序 | O(n) | 将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。 |
不稳定的排序：
稳定性一个形象的比喻，本来有两个并列第三，一排序把原来并列的顺序给变了。
比如：选择排序、快速排序、堆排序、希尔排序；
参考链接
2. 冒泡排序
image
每次都把未排序的第一个作为起始点，然后逐渐冒泡上升，之后未排序区越来越少，最终排序完成
image
1// 冒泡排序
2void bubble_sort(int a[], int n)
3{
4 int i = 0;
5 int j = 0;
6 for (i=0; i<n-1; i++)
7 {
8 // 比较相邻元素，若a[j]比a[j+1]大，则交换
9 // a[j]就像一个气泡一样“浮”到合适位置了
10 for(j=0; j<n-1-i; j++)
11 {
12 if(a[j]>a[j+1])
13 {
14 swap(&a[j], &a[j+1]);
15 }
16 }
17 }
18}
3. 选择排序
image
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
image
1// 选择排序
2void select_sort(int a[], int n)
3{
4 int i=0,j=0,min=0;
5 for (i=0; i < n-1; i++)
6 {
7 min = i;
8 // 找到最小值
9 for (j=i+1; j <= n-1; j++)
10 {
11 if (a[min] > a[j])
12 min = j;
13 }
14 if(min != i)
15 {
16 swap(&a[min], &a[i]);
17 }
18 }
19}
4. 插入排序
image
每次排序从未排序区取一个“牌”，然后往前插入(包括了两步：大的往后移，把牌放到合适位置)。
image
1// 插入排序
2void insert_sort(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 int tmp=0;
7 for (i = 1; i < n; i++)
8 {
9 // 取牌
10 tmp = a[i];
11 // 往前插的起始位置
12 j = i - 1;
13
14 // 大的a[j]都放后面，寻找出j
15 while ((j >= 0) && a[j] > tmp)
16 {
17 // 往后放一个
18 a[j+1] = a[j];
19 j--;
20 }
21
22 // 放到该放的位置
23 a[j+1]=tmp;
24 }
25}
另外还有种思路，把数据后移的过程换成交换的过程
1// 插入排序，选中的牌冒泡向前插入
2void insert_sort_2(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 //通过i选牌
7 for (i=1; i < n; i++)
8 {
9 // 冒泡向前插入(i-1 --> 0)
10 for (j=i-1; j>=0 && a[j] > a[j + 1]; j--)
11 {
12 swap(&a[j], &a[j+1]);
13 }
14 }
15 print_a(a, n);
16}
17`
5. 希尔排序
对插入排序再加一个步长的循环就是希尔排序了，例如
1[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
按照5步长排序，则相当于按列先进行排序(实际是通过下标实现的)
113 14 94 33 82225 59 94 65 23345 27 73 25 39410
排序后结果为
110 14 73 25 23213 27 94 33 39325 59 94 65 82445
多次循环后，只需要最终步长为1即可。
1// 希尔排序
2void shell_sort(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 int tmp=0;
7 int gap=0;
8 while (gap <= n)
9 {
10 gap = gap*3 + 1;
11 }
12 while (gap > 0)
13 {
14 // 取牌
15 for (i = gap; i < n; i++)
16 {
17 // 冒泡向前插入(i-gap : gap : 0), 保证每列ok
18 for (j = i - gap; (j >= 0) && (a[j] > a[j + gap]); j = j - gap)
19 {
20 swap(&a[j], &a[j+gap]);
21 }
22 }
23 gap = (gap-1) / 3;
24 }
25}
6. 快速排序
image
每次迭代都选出一个基准，左边放小的，右边放大的，最终迭代完成。
image
1// 快速排序分区
2static int partition(int a[], int p, int r)
3{
4 int x=0;
5 int i=0;
6 int j=0;
7 // x为基准
8 x = a[r];
9 // i为界限,发现小于x的，就i++，再放到i处
10 i = p-1;
11 for (j=p; j<= r-1; j++)
12 {
13 if (a[j]<=x)
14 {
15 i++;
16 swap(&a[i], &a[j]);
17 }
18 }
19 // 至此，所有小于x的都到i左边了(a[0]~a[i-1])，a[r]是x，因此交换a[i+1]和a[r]
20 swap(&a[i+1], &a[r]);
21 return i+1;
22}
23
24// 快速排序
25void quick_sort(int a[], int p, int r)
26{
27 int q=0;
28 if (p < r)
29 {
30 // 在数据集之中，选择一个元素作为"基准"（pivot）
31 // 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边
32 q = partition(a, p, r);
33 // 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
34 quick_sort(a, p, q-1);
35 quick_sort(a, q+1, r);
36 }
37}
