希尔排序

注1：本篇是基于对直接插入排序法的拓展，如果对直接插入法不了解，建议先看看直接插入排序

注2：本篇统一采用升序排序

基本思想

• 希尔排序法又称缩小增量法。
  
• 希尔排序其实是直接插入排序的改进。
  
• 其基本思想是：先选定一个整数gap，把待排序文件中所有记录分成数组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后缩小gap，重复上述步骤，当gap == 1时，所有记录在统一组内已经排好序。
  

整体插入思想

• 在直接插入排序中，我们知道最坏的情况是待排序列降序逆序的情况，如序列：8,7,6,5,4,3,2,1，这时时间复杂度为O(N²)，显然效率不高
• 而希尔排序的思想，就是先对待排序列进行预排序，使待排序列接近有序。我们知道，当待排序列接近有序时，直接插入排序法的时间复杂度接近O(N)，效率很高，因此预排序过后，就使用直接插入排序法，从而提高了效率。

预排序

• 预排序实际上也是直接插入排序，但是是将待排序列分成数组来排
  
• 根据基本思想，规定间隔为gap的数为一组
  
• 我们以数组{9,8,7,6,5,4,3,2,1}，gap= 3为例：

• 每gap为一组：
  
  
• 对第一组排序：
  
  
• 对第二组排序：
  
  
• 对第三组排序：
  
  

• 这时相较于最开始，待排序列更加接近于有序，此时我们不断缩小gap，不断预排序，直到最后gap == 1时最后使用一次直接插入排序（gap == 1时的直接插入排序实际上就是最原始的直接插入排序），使待排序列有序。
  
• 又例如：
  
  

结论

• 希尔排序实际上就是多组间隔为gap的预排序，gap由大到小
• gap越大，大的数能越快到后面，小的数能越快到前面
• gap越大，预排序之后待排序列越不接近于有序
• gap越小，预排序之后待排序列越接近于有序
• 当gap == 1时，预排序实际上就是对整个序列进行直接插入排序，排完后序列即有序
• 因此，最后一次预排序，gap必须为1.

代码实现

• 对每间隔gap的一组数据进行排序，本质上就是直接插入排序，故不作过多讲解

int end;
int temp = nums[end + gap];
while (end >= 0)
{
    if (temp < nums[end])
    {
        nums[end + gap] = nums[end];
        end -= gap;
    }
    else
        break;
}
nums[end + gap] = temp;

• 对多组间隔为gap的数据进行预排序

• 以这张图为例：
  
  
• 我们上面的步骤只是将间隔为pap的一组数据进行了排序，但待排序列不止一组间隔为gap的数据，因此我们要做到将所有间隔为gap的每组数据都进行排序。
  
• 怎么实现呢？可能最容易想到的是分别将每组间隔为gap的数据进行排序，例如上面分别对第一组，第二组，第三组排序，但是这样做效率不高，且操作复杂。因此我们要换一种想法，即把间隔为gap的数据同时排序。
  
• 如图：