【初阶数据结构】排序——插入排序
目录
- 前言
- 直接插入排序
- 希尔排序
前言
排序：所谓排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。
例如：买东西时会根据销量或价格排序综合比对，又如玩扑克牌时会将手中的牌按自己喜欢的顺序进行排序等待，排序在生活中很常见，常见的排序算法又有以下几种：
下面我们就来讲讲插入排序。
直接插入排序
直接插入排序是一种简单的插入排序法。
基本思想：把
待排序的数据逐个插入到一个已经排好序的序列中，使其同样为有序序列，直到所有的记录插完为止，得到一个新的有序序列。
实际上我们玩扑克牌时就会用到此思想：先拿起一张放手上，拿第二张时会和第一张比较大小，以此来插入，拿第三张时又会对比前两张的大小，找到合适的位置插入……
我们可以简单来看一下排序过程：
过程分析（以升序为例）：
- 将
第一个数看成是一个有序序列，从第二个元素开始逐个插入到这有序序列中。 - 当插入第i(i>=1)个元素时，
前面的a[0]……a[i-1]都已经排好序 - 此时将
a[i]的大小与按照从右至左的顺序依次进行比较，找到第一个比它小的数字，记为a[end]。 - 将
a[end]后面的数都往后挪一位，a[end+1]处插入那个元素。
具体代码如下：
//思想就像理扑克牌一样，把第一项当成有序，后面依次插入
void InsertSort(int* a, int n)//插入排序
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];//需要插入排序的值
while (end >= 0)
{
if (a[end] > tmp)//一直找到比tmp小的值
{
a[end + 1] = a[end];
end--;
}
else
break;
}
//若未找到跳出循环证明tmp最小，此时end=-1，tmp插在end+1也就是最前面
a[end + 1] = tmp;
}
}
直接插入排序的特性总结：
- 元素集合
越接近有序，直接插入排序算法的时间效率越高 - 时间复杂度：
O(N^2^)
按照最坏情况来看是逆序时，第2个数字插入前面数字往后挪1位，第3个数字插入时前面数字要往后挪两位，以此类推，到第n个数字插入时则前面的数字要往后挪n-1位，所有挪动次数相加是一个等差数列，则量级就为n^2^。 - 空间复杂度：O(1)
稳定性：稳定
希尔排序
希尔排序法又称缩小增量排序。
其基本思想如下：
- 先选定一个整数
gap，将待排序的数据分成gap组，且所有距离为gap的分在一个组。 - 对所有组
分别进行排序。 缩小gap，重新分组，对所有组别重新排序。重复上述操作，待gap为1时，则进行插入排序，使其所有数据有序。
先来看看是如何分组的：
过程分析（以升序为例）：
- 首先确定gap的初始值，这并没有一个确切的答案，在最开始首先定义gap = n(n为元素个数)，但我们不能取n作为gap，会没有任何意义，一般取
gap = gap/2或者是gap = gap/3+1作为初始值。 - 确定结束条件，即当gap>1则进入循环，然后根据
gap = gap/2或者是gap = gap/3+1来缩减gap，当循环判断gap==1时，说明在上一次循环时已经进行了直接插入排序，数列已经有序了，则不需要进入循环。
因此外部大循环可写为如下：
int gap = n;//n是数据个数
while(gap > 1)
{
//gap /= 2;
gap = gap/3 + 1;//这两种写法都可以，都能保证在最后gap=1，使其进行直接插入排序
//.....
}
下面则是单趟排序的过程：
单趟排序的过程和直接插入排序的过程差不多，我们直接来看代码：
void ShellSort(int* a, int n)//希尔排序
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;///保证最后一趟gap一定为1，进行插入排序
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];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
}
由代码发现，实际上并不是一组一组进行排序的，
希尔排序的特性总结：
希尔排序是对直接插入排序的优化。- 当
gap>1时都属于是预排序：即分组插入排序，将大的数更快放到后面，小的数更快放到前面，目标是使序列接近有序 - 当
gap==1时，就是直接插入排序，此时序列已经接近有序，再插入排序就会快很多。 - 希尔排序的时间复杂度不好计算，可以记住大约在
O(N^1.3^)即可。
感谢大家观看，如果大家喜欢，希望大家一键三连支持一下，如有表述不正确，也欢迎大家批评指正。
