手撕插入排序及其优化（希尔排序）
点击蓝字
关注不迷途
插入排序，遍历未排序元素，插入到有序的数组内。
插入排序的实现很简单，但是时间复杂度很糟糕，平均时间复杂度为O(n2)。
那还有没有优化的地方呢？
可以发现，在插入之前，需要定位元素插入的位置，而上面的做法是通过遍历比较来进行定位，时间复杂度相对来说很高，O(n)。
查找步骤可以使用二分查找来进行优化。
定位元素位置可分为几种情况。
单区间只有一个元素时，只需要判断是否要交换该元素即可。
当区间有两个或两个以上元素时，先与边界值进行判断，如果小于等于最左边元素，最后元素的位置应该是最左边的位置。
如果大于等于最右边的元素，则元素的最终位置不变。
对边界值进行判断后发现不是上面两种情况，则说明元素最终应该插入到区间内。
先对区间进行二分，判断元素在哪边，然后缩小区间，直到区间只剩下两个元素，退出二分循环。
最后元素插入位置为为两个元素的中间。
插入排序的最好时间复杂度是O(n)，当数组内没有逆序对时。
插入排序的时间复杂度和逆序对的数量成正比，所以可以通过减少逆序对来实现插入排序的优化。
希尔排序是插入排序的优化，希尔排序也称缩小增量排序，通过增量把数组分为几组，每组都执行插入排序。
增量序列逐渐减小，直到增量为1，同时每次对分组进行排序后，逆序对都逐渐减少，逆序对的减少对下一次分组的插入排序效率有所提高。
希尔排序是第一个突破O(n2)时间复杂度限制的排序算法，其时间复杂度受增量序列影响。
往期推荐
不迷途
关注不迷途
您的关注，是对我最大的认可
喜欢本篇内容顺便点个在看吧