简要步骤

希尔排序是一种直接插入排序的优化排序方法。它通过设定的步长进行分组，对每组中的数据进行直接插入排序，随着步长的减少，每组中的数据也随着增加，直到步长减少为1，那么整组数据也就变为有序的了。

初始序列：{ 4, 6, 3, 0, 2, 5, 1 }

大体上来说，希尔排序就是通过以一定步长分组后对数据进行预处理，来减少最后步长为1时的工作量。

性能分析

时间复杂度：分析希尔排序的时间复杂度是一个比较困难的问题，因为它的时间复杂度和步长序列有着密不可分的关系。本篇文章我们选择的是希尔步长序列，在该序列下，时间复杂度可以达到约O( N^1.5 )。

空间复杂度：无须赘述，和直接插入排序同样是O( 1 )；

稳定性：直接插入排序是稳定的，而希尔排序是不稳定的，因为相等数据的位置可能会交换。为了证明希尔排序是不稳定的，我们可以创建一个结构体，其中的data是数据本身的值，location是数据的初始位置，以序列{ 3, 2, 2, 1 }为例，最终我们发现两个{ 2 }的前后位置关系发生了改变。代码放在了最后。

优化

对希尔排序的优化主要就是改变其步长，在其他一些步长序列下，时间复杂度可以下降到O( N^1.3 )左右。

希尔步长序列：{ Length/2, Length/4, … , Length/(2^k) }

Hibbard序列：{ 1, 3, 5, … , 2^k-1 }

Sedgewick序列：{ 1, 5, 19, 41, …… }     (该序列是如何得到的呢？有兴趣的同学可以自己查一下)

代码

希尔排序：

#include <stdio.h> /* * 希尔排序 */ void ShellSort(int arr[], int length) { int step; int i,j,temp; for(step = length/2; step >= 1; step /= 2) { for(i = step; i < length; i++) { temp = arr[i]; for (j = i - step; j >= 0 && arr[j] > temp; j -= step) arr[j + step] = arr[j]; arr[j + step] = temp; } } } int main() { int arr[] = {4,6,3,0,2,5,1}; int length = sizeof(arr)/sizeof(arr[0]); printf("排序前:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } ShellSort(arr, length); printf("\n排序后:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]); } return 0; } 带位置的希尔排序（用来判断排序是否稳定）：

#include <stdio.h> #include <stdlib.h> /* * 带位置的希尔排序 */ typedef struct Record { int data; int location; }Record; void ShellSort(Record *arr[], int length) { int step; int i,j; Record *temp; temp = (Record*)malloc(sizeof(Record)); for(step = length/2; step >= 1; step /= 2) { for(i = step; i < length; i++) { temp = arr[i]; for (j = i - step; j >= 0 && arr[j]->data > temp->data; j -= step) arr[j + step] = arr[j]; arr[j + step] = temp; } } } int main() { // int arr[] = {4,6,3,0,2,5,1}; // int length = sizeof(arr)/sizeof(arr[0]); int length = 4; Record *arr[length]; for(int i=0; i<length; i++) { arr[i] = (Record*)malloc(sizeof(Record)); } arr[0]->data = 3; arr[1]->data = 2; arr[2]->data = 2; arr[3]->data = 1; arr[0]->location = 0; arr[1]->location = 1; arr[2]->location = 2; arr[3]->location = 3; printf("排序前的序列:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]->data); } printf("\n排序前的位置:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]->location); } ShellSort(arr, length); printf("\n\n排序后的序列:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]->data); } printf("\n排序后的位置:"); for(int i=0; i<length; i++) { printf(" %d",arr[i]->location); } return 0; }