sort:让我们来提升一下插入排序的性能吧！

插入排序upupup —> 希尔排序

---

插入排序是一个平均时间复杂度为O(n^2)的算法，他的效率其实并不算高效，不过，他有两个特点

• 在大多数元素都是有序的情况下，工作量很少
  很明显，在大多数元素都是有序的情况下，数组中的元素自然不需要频繁的交换
• 在元素较少的情况下，插入排序的工作量很少
  只要n很小，那么工作量自然会很少

要优化插入排序，自然要从这两点出手。

那么，我们怎么才能让一个数组大量元素有序呢？这个时候我们就需要对元素进行一些预处理了。比如，我们可以先将数组的元素两两分组先进行排序。我们首先可以先为元素设立跨度，在这里，元素有8个，那么我们取一半，就每隔4个元素视为一组，这样的话，就可以达成两两分组的目的了

5 8 6 3 9 2 1  7
|-------|       
  |-------|     
    |-------|   
      |--------|

首先，先这样进行排序，那么，这一次的排序粗略来说，确实是多次的元素很少的排序，而且，排序出来的结果也是使得数组的元素变得有序起来了，然后，我们在将跨度减少从4变成2

5 2 1 3 9 8 6 7
|---|---|---|
  |---|---|---|

首先我们先看看发生了什么，在第二组数据当中，元素就已经是基本有序的状态了，可以看出，在不断的按照分组进行排序的过程当中，元素是趋于有序的，也就是说，虽然，使用的都是插入排序的方法，但是，每一次的排序都充分的或运用了元素少的特点，或运用了大量元素有序的特点，从而从整体上提升了插入排序的效率。

我看看看跨度2排序完的结果

1 2 5 3 6 7 9 8

确实，已经是大量有序的情况了。

之后的跨度就是1，也就是普通的插入排序了。

这种希尔排序的方式，叫做朴素的希尔排序，他可以将平均时间复杂度控制在o(n^2)之下

vector<int> sortArray(vector<int>& nums) {
       int len = nums.size();
       while(len > 1)
       {
           len /= 2;
           for(int i = 0;i < len;i++)
           {
               for(int j = i + len;j < nums.size();j += len)
               {
                   int insert = nums[j];
                   int k;
                   for(k = j - len;k>=0 && nums[k]>insert;k-=len)
                   {
                       nums[k + len]=nums[k];
                   }
                   nums[k + len]=insert;
               }
           }
       }

       return nums;
   }

当然，在最坏的情况下，希尔排序的时间复杂度甚至可以超过插入排序，比如以下的这个数组

2 1 5 3 7 6 9 8

在这个情况下，无论是分割4，2的时候，都是没有办法对数组进行排序的，也就是说预处理就是做了无用功，对于这种情况，就是白白的浪费了性能在预处理之上。

不过，这种情况也是可以避免的，在朴素的方法下，希尔排序的区间增量是等比的，因此，比较容易出现盲区。为了防止这种盲区的出现，希尔排序的每一轮的增量应该是互质的，因此，有很多人提出了很多种增量的方式

比如hibbard增量，他的表达公式是2^k-1，也就是1，3，5，7….的序列。在这个序列下，希尔排序的最坏时间复杂度为O(n^(3/2))

再比如sedgewick增量，他的表达式是(9 4^k- 9 2^k + 1,4^k - 3 * 2^k + 1),其序列为1,5,19,41,109…..在这种序列下希尔排序的最坏事件复杂度为O(n^(4/3))