【初阶数据结构】排序—

【初阶数据结构】排序——插入排序

前言

排序：所谓排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。
例如：买东西时会根据销量或价格排序综合比对，又如玩扑克牌时会将手中的牌按自己喜欢的顺序进行排序等待，排序在生活中很常见，常见的排序算法又有以下几种：
在这里插入图片描述
下面我们就来讲讲插入排序。

直接插入排序

直接插入排序是一种简单的插入排序法。

基本思想：把待排序的数据逐个插入到一个已经排好序的序列中，使其同样为有序序列，直到所有的记录插完为止，得到一个新的有序序列。

实际上我们玩扑克牌时就会用到此思想：先拿起一张放手上，拿第二张时会和第一张比较大小，以此来插入，拿第三张时又会对比前两张的大小，找到合适的位置插入……
我们可以简单来看一下排序过程：
在这里插入图片描述
过程分析（以升序为例）：

将第一个数看成是一个有序序列，从第二个元素开始逐个插入到这有序序列中。
当插入第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--;}elsebreak;}//若未找到跳出循环证明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;}elsebreak;}a[end + gap] = tmp;}}
}