排序——希尔排序

希尔排序实际上是插入排序的优化，所以要先介绍插入排序。

目录

插入排序

思想

演示

代码实现

总结

希尔排序

思想

演示

代码

总结

---

插入排序

思想

     又称直接插入排序。它的基本思想是将一个值插入到一个有序序列中。直至将所有的值都插入完。

演示

     假设数组某个位置的下标是end，end + 1对应的值为temp。

     让arr[end]，temp进行比较如果arr[end]＞temp，将arr[end]向后移一位

在让temp与end的前一位进行比较，如果大于那就重复上述操作，反则跳出循环。注意end只能大于等于0。

     离开循环后会存在上面图示的情况。我们只需要用temp把它给替换掉。

     上面说的是一次插入，所以要再在外面套一层循环把所有的值都插入一次。

代码实现

//插入牌序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int temp = arr[end + 1];while (end >= 0){if (arr[end] > temp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = temp;}
}

总结

1. 当序列越有顺序时，插入排序的时间效率就越高。
2. 时间复杂度：O(N^2)（虽然时间复杂度是N^2，那是在逆序的序列情况下，在现实中这种情况一般不会出现）
3. 空间复杂度：O(1)

希尔排序

思想

     又称缩小增量排序。它的基本思想是将整个待排元素序列分割成若干个小组，相隔一个gap为一组（gap是一个整数），各小组分别进行插入排序，然后缩减gap再进行排序，重复上述操作。当gap==1时，整个序列中的元素基本有序，在对全体元素进行一次插入排序。

演示

     假设gap=3，每隔gap个为一组分组如下：

   遍历一次结束条件：在3对应的下标处加一个gap会正好造成非法访问，所以结束条件是下标小于n - gap。  

     下面的操作就和插入排序一样只不过是相隔gap个插入，经过一次一次的排序序列会变得更有序。

在上面提到gap会逐渐变小，那它怎么变小呢？一般是gap = (gap / 3) + 1（这是相对来说比较合理的记住即可）。当gap小于1时即排完序离开循环即可。

代码

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

总结

1. gap＞1：预排序，目的是让序列变得更有序。
2. 时间复杂度：O(N^1.3)
3. 空间复杂度：O(1)