插入排序与希尔排序（C语言实现）

1.插入排序

由上面的动图可以知道插入排序的逻辑就是从第一个元素开始往后遍历，如果找到比前一个元素小的（或者大的）就往前排，所以插入排序的每一次遍历都会保证前面的数据是有序的，接下类用代码进行讲解。

我们这里传两个参数，一个是数组，一个是数组元素的个数。

排序接口我们采用大事化小的想法来进行讲解， 我们先来思考单趟遍历要达成的目标。我们每次遍历的主角其实就是我们要操纵的那一个元素，比如我们要排第四个元素，按照插入排序的逻辑，前三个元素我们是已经有序了，所以我们接下来的操作就是将我们的主角元素跟前面的元素进行比较，如果元素比前面的小我们就跟前面的交换（我们这里实现升序排序），以此循环往复，直到遇到比它还小的元素我们就终止循环，所以我们就可以理解里面这层while循环的意思了，循环结束的时候不要忘记把元素放到停止循环的end下标位置上，有的同学可能一时间没有理解到为什么最后下标的位置是end+1，其实这是因为在结束while循环之前我们的end是减一过的，所以才要给他加回去。

然后我们的for循环就是控制我们的主角啦，就是控制后面的每一个元素跟前面已经排序好的元素进行比较。

插入排序最坏的时间复杂度O（n^2）

最好的情况就是这个数组已经有序的时候时间复杂度为O(n)

2.希尔排序

 上诉动态演示就是希尔排序，大家看到这个演示的时候肯定会两眼一黑，看不懂它是如何进行排序的，希尔排序的逻辑是有点复杂，但是我相信在我讲了它的实现思路之后对希尔排序也会有一个比较清晰的理解。

希尔排序可以相当于插入排序的pro版本，这是因为它的逻辑虽然比插入排序复杂，但是却是建立在插入排序之上，插入排序的核心思想是遍历每一个元素去跟前面已经排好序的元素进行比较，希尔排序有一个预排序的过程，就是说通过给定一个gap（变量名）来控制一个间距，使下标为end的元素跟end+gap来比较，这个预排序就是使一个无序数组接近有序数组，在预排序完成之后再用插入排序使数组有序。其实到这里大家就会发现，如果用这里的思想去理解插入排序的话，插入排序实际上就是gap为1的情况嘛。

我们用代码来加深理解。

这是希尔排序的代码，我们可以看到gap的初始值设置的是数组的长度，那下面的while循环时什么意思呢？我们先来理解最里层的while循环，最里层的while循环是不是有一种很眼熟的感觉?它就是我们的插入排序的思想，只不过插入排序是间隔为一进行比较，希尔排序是间隔为gap进行比较，我们再看外面这层for循环，这层for循环控制的就是end的下标，跟插入排序也非常的相似，只不过这里的for循环结束的条件是n-gap，因为既让我们当前下标的元素要跟后一个相比，那总不能让end+gap的下标超出界限吧。

最后再来看最外层的while循环，它的作用就是控制gap的值。我们这里得要知道gap越大，这一趟预排序就越不能做到很有序的程度，但好处就是耗时短，gap的值越小就是相反的情况，但是不要忘记了，一个数组越有序，插入排序处理得就越快，希尔排序也是一样的，所以为了达到理想的时间复杂度，我们的做法就是将gap的值由大到小。

接下来来说说gap的值如何来设置，gap的值该如何来设置是没有一个统一的说法的，但是有一个大佬想出的一个比较好的方法是用数组长度来充当第一次的gap值，每一次循环完就将gap的值/3+1这是为了避免上一个gap为二的时候下一次gap直接变为0了。

所以我们的希尔排序最后一趟就是我们的插入排序，只不过这个时候数组已经非常接近有序了。

我们的希尔排序最坏的情况下时间复杂度是O(n^2),平均是O(n^1.3)。