希尔排序是D.L.Shell于1959年提出来的一种排序算法，在这之前的算法的时间复杂度为O(n²),希尔排序算法是突破这个时间复杂度的第一批算法之一.
希尔算法基于一种增量序列，将待排序序列分组，分别对每一组进行插入排序。希尔排序在随机情况下，算法的效率表现很优秀。
回顾之前讲过的插入排序，插入排序在序列元素较少的情况下，序列基本有序的情况下效率较高，希尔排序在插入排序基础上去实现这两种苛刻的要求，也就是使得每一次进行插入排序的待排序序列元素个数较少，并使得整体元素更加有序。
使得待排序序列元素减少，那么可以使用分组，分组的策略是基于增量，可理解为相差固定个数的的元素组成组，分别对每一组进行排序，每一组的元素个数就会减少。每一组的元素趋于有序，那么整个待排序序列也越来越趋于有序。
我们在说到分组时，提到增量，因为增量关系到要分多少组，这个增量的算法至今没有确切的答案，但是根据行业经验，增量 = 数据个数 / 3 + 1.
在进行希尔排序中，这个增量循环调用这个增量计算公式递减，直至增量为1时，对所有元素进行最后一次插入排序。
希尔排序是不稳定的排序算法，希尔排序平均时间复杂度n*log2n，最坏时间复杂度为O(n²)。下面我们来介绍希尔排序：
 

待排序序列为：9,1,5,8,3,7,4,6,2，当增量为3时，将待排序序列分为3组：
第一组：9,8,4
第二组 : 1,3,6
第三组 : 5,7,2
分别对每一组进行插入排序，排序后结果为：4,1,2,8,3,5,9,6,7
递减增量为2，再分组：
第一组：4,2,3,9,7
第二组：1,8,4,6
分组对这两组进行排序，排序后结果为: 2,1,3,5,4,6,7,8,9
继续递减增量为1，对整体数据进行一次插入排序，排序结果为:
1,2,3,4,5,6,7,8,9
实现代码为:

void PrintArray(int arr[], int len){ for (int i = 0; i < len; i++){ printf("%d ", arr[i]); } printf("\n"); } //希尔排序 void ShellSort(int arr[], int len){   int increasement = len; do{   //通过算法递减增量 increasement = increasement / 3 + 1; //获得每一组的第一个元素下标 for (int i = 0; i < increasement; i++){ //根据第一个元素下标+增量，遍历每一组元素 for (int j = i + increasement; j < len; j += increasement){ //对当前组进行插入排序 if (arr[j] < arr[j - increasement]){   int temp = arr[j]; int k = j - increasement; for (; k >= i && temp < arr[k]; k -= increasement){ arr[k + increasement] = arr[k]; } arr[k + increasement] = temp;   }   }   }   } while (increasement > 1); } int main(){   int arr[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 }; int len = sizeof(arr) / sizeof(int); //排序前打印 PrintArray(arr, len); ShellSort(arr, len); //排序后打印 PrintArray(arr, len);   return EXIT_SUCCESS; }

本文版权归乐鱼播客C++培训学院所有，欢迎转载，转载请注明作者出处。谢谢！
作者：乐鱼播客C/C++培训学院
首发：http://www.itcast.cn/c/