目录

插入排序

         插入排序代码实现：

        插入排序思路：

        希尔排序：

       什么是希尔排序：

       希尔排序代码实现：

        希尔排序思路：

---

插入排序（稳定）

         假设有这样一个数组，想要从小到大进行排序：

int[] array = {4,9,5,8,6,2,10,7,3,1};

         插入排序代码实现：

public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int ret = arr[i];int j = i - 1;for (; j >= 0 ; j--) {if(arr[j] > ret) {arr[j+1] = arr[j];}else {//arr[j+1] = ret;break;}}arr[j+1] = ret;}}

         代码运行结果：

        

        可以看到，结果是从小到大排序的。

        

        插入排序思路：

        

         假设有个待排序数组（黑色数字），定义一个 i 下标，一个 j 下标，再定义一个记录i下标的值的ret。

        首先，i 下标从 1 位置开始，j 下标在 i - 1位置开始，当 j 下标的值比 ret 的值大，把 j 下标的值给到 j+1 的位置。反之 把ret 的值给到 j+1的位置。以此往复。

        值得注意的是，比如数组的最小的元素（上图的是0）， j 会到达下标为 -1 的位置，此时，循环里的  arr[j+1] = ret; 这句代码就执行不到了，意思就是数组最小元素 0 放不到下标为 0 的位置。所以在外面 加上一句 arr[j+1] = ret; 代码。这句代码和 循环里的这句代码重复了，就把 循环里的这句代码注释了。

        

 希尔排序（不稳定）：

       什么是希尔排序：

          把待排序数据分成多个组，所有距离为的记录分在同⼀组内，并对每⼀组内的记录进行插入排序。然后，重复上述分组和排序的过程。当到达=1时，所有记录在统⼀组内排好序。

        什么意思呢？

        如图：

        

         先假定 gap的大小，这里初始的 gap 是5，让 每个数据之间都相差 距离为 gap 的大小，如果后面的最远的数据相差比 gap小就 不相连，这样就为一组了。下一个 组 从第二个数据开始，直到包含所有数据。分组就结束了。

        然后，对其中的一趟的 每一组进行插入排序，再不断缩小gap的大小，直到gap的大小为1，gap的大小为1就是一次完整的插入排序了。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

        所有，可以说希尔排序是对插入排序的优化。

         一样，我们假设有这样一个数组，想要从小到大进行排序：

 int[] array = {4,9,5,8,6,2,10,7,3,1};

       希尔排序代码实现：

 public static void shellSort(int[] arr) {int gap = arr.length / 2;while(gap > 0) {shell(arr,gap);gap /= 2;}}public static void shell(int[] arr,int gap) {for (int i = gap; i < arr.length; i++) {int ret = arr[i];int j = i - gap;for (; j >= 0 ; j -= gap) {if(arr[j] > ret) {arr[j+gap] = arr[j];}else {//arr[j+1] = ret;break;}}arr[j+gap] = ret;}}

        希尔排序思路：

        

         结合上图，这是 gap 为 2 的时候的情况，与插入排序类似，结合代码看，把红色组别看成一组数据，先让 下标 i 等于 gap的位置，j 在 i - gap 的位置，确保他们是在红色组别位置进行插入排序，下一次，i 加加，到了绿色组别位置，再让 j 在 i - gap 的位置，确保他们是在绿色组别位置进行插入排序。可以看出，他们是在红色和绿色组别交替进行插入排序的。

        直到 gap 为 1 ，就可以看作一次普通的插入排序了。

        

        至于起始的 gap 选多大是无法给出正确答案的，希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算。