数据结构-直接插入和希尔排序

这次，我们来讲数据结构的排序的直接插入。

一：排序的思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

相当于，我们打牌如上图时，我们一般都会使用直接插入排序的方法。

即：在3和9直接插入，对吧。

同样，我们这里的直接排序也是按这种方法来思考。

那么，我们先来上它的动图，来方便我们更清楚。

 

 步骤讲解：（升序）

1.一开始的时候，当第一个的时候，它肯定是有序的，所以我们从第二个数开始插入并比较。

2.先把第二个数用临时变量存起来，再去比较，如果它比前面对比数还要小，就将前面对比数挪到后面，临时变量再去跟更前面的数依次比较。

3.如果临时变量大于对比那个数，就插入到对比数的后面。

4.循环（数据向前插入）进去，直到全部的数都插到正确的位置。

void InsertSort(int* a, int n)
{//整个for (int i = 1; i < n; i++){//单一个int end = i - 1;int temp = a[i];while (end >= 0){if (a[end] > temp)   //如果对比数大于存入临时的，就对比数往后挪{a[end + 1] = a[end];end--;}else   //如果对比数小于存入临时的，就跳出循环{break;}}a[end + 1] = temp;  //在对比数的后面插入数}}

 

直接插入排序的特性总结：

 

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

就比如是

你每次插入是都比前面那个数大，那么你是不是就不需要挪动数据了，

假设你有n个数据，按照上面的情况，你执行的次数就是n-1,这样效率是不是就高了。

此时的最好时间复杂度：O(N)。

 

2.

那么最坏的情况呢？

就是逆序。这样你每次插入的时侯，都是要跟前面的对比数挪动

此时的 时间复杂度：O(N^2)。

 

3. 空间复杂度：O(1)，它是一种稳定的排序算法

 

4. 稳定性：稳定

 

优化排序---希尔排序

上面我们已经知道，插入排序的时间复杂度O(N^2).

那么有什么办法使他们的效率更高一点呢？

这里大佬们提出了希尔排序的方法。

思路：

1.用间隔为gap的变量分别对每组数插入

2.预排序：它的目标就是接近有序

3.最后再直接插入

这样的方法会大大提高效率。

比如说，你看：按照下面的话分组

这一趟排序完，是不是就看起来比没有排时变有序了。 

 

 

 

 

这样，一趟趟地回来，到gap==1时，就只需挪隔壁的数字比较，所以大大提高了直接插入的效率。

 

比较：

我们知道上面直接排序：

直接插入：完全逆序时：

 它比较执行的次数（1+2+3……n-1）次

根据等差数列的公式：n^2/2-n/2;

那么，我们使用希尔排序，（用gap分组）

gap=gap/4时

分成两部分：

那么它的次数（1+2+……+n/2-1）+（1+2+……+n/2-1）

那么计算得到：n^2/4-n/2;

相比，你看，是不是就提高了效率。

 

gap=gap/2

假设为n，则分成3部分

执行的次数：（1+2+3+……n-1）*3

计算得： n^2/6-n/2;

 

类比得：当我们分的部分越多，执行的次数会减少。

有以下规律：

当分成部分k，执行次数：

1/k*n^2/2-n/2

 

当gap越小，跳得越慢，越有序，当gap越大，跳得越慢，越无序。

那么我们发现，当gap很小时，它的次数本来是n^2/2-n/2，但是，，我们考虑到之前我们已经经过预排序了，已经很接近有序了，所以按照最好的情况来算。

 

总结：

 希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。 

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

根据大佬们的推算，一般都是gap=(gap/3）+1常用

 

 

int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < gap; i++){for (int i = 0; i < n - gap; i += gap){//单个int end = i;int temp = a[i + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}}}

好了，选择排序和希尔排序就写完了。

最后，学路漫漫，永无止境，一点一点进步吧！