一、算法实现原理
希尔排序是在直接插入排序的基础上进行的改进算法，其基本思想就是先选定一个整数gap，把待排序序列中的所有记录分为gap组，其中间隔为gap的记录分在同一组，并对每一组进行直接插入排序。然后再取gap=gap-n（n为小于gap的整数），重复上述分组插入操作，直到gap=1时，所有记录在同一组中，进行直接插入排序，排序完成。
例：
其中不断的分组进行直接插入排序的过程，就是将序列调到基本有序的过程。
基本有序：小的数据尽量靠前，大的数据尽量靠后，中间的数据尽量靠中间。
二、代码实现
1.完整代码
#include<stdio.h> void ShellSort(int* array, int size);//希尔排序 void PrintArray(int* array, int size);//数组打印 int main() { int array[] = { 5,0,7,4,1,2,9,3,6,8 }; int length = sizeof(array) / sizeof(array[0]); printf("排序前："); PrintArray(array, length); ShellSort(array, length); printf("\n排序后："); PrintArray(array, length); return 0; } void ShellSort(int* array, int size) {//希尔排序 int gap = 3; while (gap > 0) { for (int i = gap; i < size; i++) {//默认分组内第一个元素为有序序列 int end = i - gap;//标记分组内已排序序列最后位置下标 int key = array[i];//依次拿取数组内元素 while (end >= 0 && key < array[end]) {//key从前往后比较：小于当前元素，继续往前走 array[end + gap] = array[end];//将当前元素往后移一个位置（组内） end -= gap; } array[end + gap] = key;//key大于等于当前元素，插入到当前位置之后（组内） } gap--; } } void PrintArray(int* array, int size) {//数组打印 for (int i = 0; i < size; i++) { printf("%d ", array[i]); } }
2.测试结果
三、性能分析
1.特性总结
1.1希尔排序是对直接插入排序的优化。
1.2当gap>1时都是预排序的过程，目的是让数组更接近于有序状态。当gap=1时，数组已经接近有序，再经过一趟直接插入排序完成排序，从而提高排序的效率。
1.3因为gap的取值方法很多，导致希尔排序的时间复杂度很难计算，因此给出的时间复杂度都不固定。按照Knuth提出的方式取值（gap=），一般按照O（）到O（）来算。
2.性能分析
1.时间复杂度：O（
）到O（
）
2.空间复杂度：O（1）
3.稳定性：不稳定
