一、算法介绍
1.算法思想
希尔排序是在直接插入排序的基础上进行的改进算法，其基本思想就是先选定一个整数gap，把待排序序列中的所有记录分为gap1组，其中间隔为gap的数据分为同一组，并对每一组内部进行直接插入排序，然后再取gap=gap-n（n为小于gap的整数），重复上述操作，直到gap=1时，所有记录在同一组中，最后在进行一趟进行直接插入排序，从而完成排序。
2.算法流程
其中不断的分组进行直接插入排序的过程，就是将序列调整到基本有序的过程。
基本有序：
小的数据尽量靠前，大的数据尽量靠后，中间的数据尽量靠近中间，即为基本有序。
二、算法实现
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.测试用例及结果
测试用例：
array[]={5,0,7,4,1,2,9,3,6,8}
测试结果：
三、性能分析
1.特性总结
1.1希尔排序是对直接插入排序的优化。
1.2当gap>1时都是预排序的过程，目的是让数组更接近于有序状态。当gap=1时，数组已经接近有序，再经过一趟直接插入排序完成排序，从而提高排序的效率。
2.时间复杂度
因为gap的取值方法很多，导致希尔排序的时间复杂度很难计算，因此给出的时间复杂度都不固定。按照Knuth提出的方式取值（gap=），一般按照O（）到O（）来算。
3.空间复杂度
因为算法中除了定义一些临时变量外，没有借助额外的辅助空间，所有希尔排序的空间复杂度为O(1)。
4.稳定性
虽然希尔排序的实质还是利用了直接插入排序，且直接插入排序是稳定的，但是希尔排序在对直接插入排序的序列进行分组时，是按照相同一定间隔的元素为一组，然后在组内进行直接插入排序，所以在整个序列上来看还是会改变相同元素的相对位置，所以希尔排序是不稳定的。
