2020-12-14

直插排序：

数组类：

以升序序列为例：

使用i标记排未排好序列的index，记录下该数，tmp = arr[i]，排好序列则为i-1，默认第一个数字已经排好，之后j=i-1，j--从后让往前找比该数小的数，如果不比该数小，则往后退一位：arr[j+1] = arr[j];，如果比该数小则退出，同时arr[j+1] = tmp;则完成一次插入。

链表类：

以降序序列为例：

使用两个指针p,q，和一个沉默链表头，p为排序完成序列的末尾，一个指针为已经排序序列的头部。如果q->val<p->val,则直接连接，如果大于，则使用cur一个辅助指针，从表头位置开始找下一个值小于q->val的结点，插入到该节点后面。

希尔排序：

数组类：

引入gap间隔值来分治直差排序算法，因为直插排序算法的，在序列越短的情况下效率越高。故而使用gap来分治子序列。每一个子序列是数组位置相差gap的数字串起来的。

同直插排序算法，默认序列的第一个位置已经排好序，则我们从gap位置开始往后使用直插排序即j = gap，同时要注意我们是对每一个子序列使用直插排序，故而两数之间的位置差应该为gap。该数在子序列中排序完成后j++，知道j==n-1，则gap/=2,直到gap==1，则希尔排序完成。

希尔排序优化了直插排序的原因是，它通过分治子序列的操作，让我们的序列变成一个较为有序的序列，可以减少我们的插入移动次数。

最后，在已排好序的序列中，我们可以考虑使用二分查找降低查找的时间复杂度使得其得到优化。