目录
- 1. 插入排序
- 1.1 基本概念
- 1.2 实现思路
- 1.3 代码部分
- 2. 希尔排序
- 2.1 为什么会有希尔排序?
- 2.2 基本概念
- 2.3 实现思想
- 1)单组排序
- 2)多组排序
- 2.4 代码部分
- 3. 总结
1. 插入排序
1.1 基本概念
把待排序的记录逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
- 实际中我们玩扑克牌时,梳理牌的过程,就用了插入排序的思想
假设n个数,n-1的数已经是排序好的(n>1,因为1个数默认是有序的),把第n个数插入到合适的位置,依次将数据插入到排好序的合适位置,直到所有数据都有序,这样长度为n个数就排好序了。
1.2 实现思路
思路(以升序为例)
- 假设第一个数据(下标0)有序,后面的
n-1
个数据都需要插入到有序数组里 - 保存有序数据后面一个数据(tmp)
- 移动数据,需要把新数据插入有序数据中的合适位置
(tmp < end)
- 移动数据停止条件有两个:
- 最坏情况:tmp比全部有序的数据要小,有序数据从头到尾都需要移动,end移动到-1,说明移动完成。
- 当tmp > end下标的数据,说明已经有序了。
- 插入数据到end+1的下标位置,因为end下标的数据是小于tmp。
1.3 代码部分
// 插入排序(升序)
void InsertSort(int* a, int n)
{ // i迭代n - 1结束,到n结束会越界,因为需要访问未排序的数据(i+1 == n+1),就会越界for (int i = 0; i < n - 1; i++){int end = i; // 有序的个数int tmp = a[end + 1]; // 需要插入的新数据(未排序的数据)// 新的数据想要插入都有序数据中,需要移动数据,插入到合适的位置// 以升序为例,最坏情况:新数据比全部有序的数据要小,有序数据都需要移动// while和if条件合并判断如下while (end >= 0 && tmp < a[end]){a[end + 1] = a[end];end--;}while (end >= 0){// 新数据小于有序数据就要移动数据if (tmp < a[end]){a[end + 1] = a[end];end--;}else{// 已经有序break;}}// 插入数据到end+1的下标位置,end < tmpa[end + 1] = tmp;}
}
2. 希尔排序
2.1 为什么会有希尔排序?
直接插入排序有缺陷,就是数据是接近逆序或逆序的时候,排的非常慢,效率很低,但是直接插入排序在数据接近有序的情况下,效率很高,而希尔排序就是直接插入排序的优化,他就是能解决数据逆序排的慢问题。
2.2 基本概念
希尔排序法又称缩小增量法,插入排序的优化。希尔排序法的基本思想是:先选定一个整数(gap),把待排所有数据分成gap个组,所有距离为差相同的数据分在同一组内,并对每一组内的记录进行排序。然后缩小gap,重复上述分组和排序的工作。当到达gap=1时,所有数据在统一组内排好序。
2.3 实现思想
排序分为两步:
- 预排序 gap > 1,目的是让数据接近有序
- 直接排序 gap = 1,目的是数据有序
1)单组排序
假设gap = 3,逆序数组排一组序
从上图看到,在一组数据中最大值就排到最后的位置
代码演示:
int gap = 3;for (int end = 0; end < n - gap; end += gap){int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}
这里我们可以发现,单趟排序和直接插入排序,大同小异,只不过把1的位置换成gap。
2)多组排序
多趟排序,相比于单趟,单趟只能排一组为相差gap的数,而多趟可以排多组相差gap的数。
实现起来也很简单,只不过是让end的递增为1(end++),只不过未排序的数据以当前end+gap,就能相差gap,分组数据同时排序了,不过需要注意的是结束条件 end < n - gap
,否则会造成越界,因为未数据是保存的是当前end+gap(a[end + gap]),大家可以看下图
gap为4,逆序数组排多组序
从结果来看上面的数据不仅没有排成接近有序,反而变得更乱了,但是他排的很快,因为每次递增gap,最终结束条件是n -gap
,而且能让大的数越快排到后面
gap为3,逆序数组多趟排一组序
上图显示一组的多趟排序,相同颜色为一组,可以看到将数据变得接近有序了,我们只需要在缩小gap,数据会越来越有序,直到gap=1,直接插入排序。
所以如:排升序
- gap越大,大的数越快到后面,小的数越快到前面,但是预排序完,越不接近有序
- gap越小,序列越接近有序
所以我们可以先让gap很大,再让gap很小,这样排序完,就可以很好的解决逆序问题,同时效率相比直接插入排序,大大提升
希尔排序和插入排序最大区别就是分组排序,不像插入排序每次连续数据比较,差距为1
gap设置多少合适呢?
希尔排序会根据数据的个数来计算出gap,以达到gap就合适的距离。
最好gap是每次gap / 3
或gap / 2
gap / 3:时间复杂度 O ( l o g 3 N ) O(log_3N) O(log3N),gap / 3 / 3 / 3 / 3 / …… = 0
gap / 2:时间复杂度 O ( l o g 2 N ) O(log_2N) O(log2N),gap / 2 / 2 / 2 / 2 / …… = 1
注意gap / 3,不能保证最后结果是1,我们需要在运算后+1,如6 / 3 = 2,2 / 3 = 0,0就不能满足我想要的插入排序。
gap / 3,官方总结算出的时间复杂度是 O ( N 1.3 ) O(N^{1.3}) O(N1.3)
2.4 代码部分
这里注释写的并不多,因为大多数地方是和直接插入排序相似,直接插入排序注释写的比较详细
// 希尔排序(升序)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// 缩小gap,最后加1,是确保最后gap=1,为直接插入排序gap = gap / 3 + 1;// 一次排多组差距为gap的数据for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];}else{break;}}a[end + gap] = tmp;}}
}
3. 总结
直接插入时间复杂度是 O ( N 2 ) O(N^2) O(N2),比如在排逆序数据的时候,但是在有序或接近有序的时间,效率很高,所以希尔排序就对这个缺陷进行了优化,预排序就可以很好解决的这个问题,希尔排序平均复杂度是 O ( N 1.3 ) O(N^{1.3}) O(N1.3)