希尔排序的时间复杂度，最好的情况下仍然是正序时，可达到O(n),平均复杂度为O(nlogn)。
算法思想：
采用跳跃式处理数组，使得数组粗粒度的实现基本有序。在进行细粒度的处理，最终使得网络在跳越数为1时，实现基本有序的排序，以减少插入排序的复杂度。
主要程序：
void shellSort(int *arr,int length){ int i,j,k; int increment = length; while(increment>0){ if(increment != 1) increment = increment/3+1; else break; for(i = increment; i<length; i++){ if(arr[i] < arr[i-increment]){ k = arr[i]; for(j=i-increment; j>=0 && k < arr[j] ; j-=increment){ arr[j+increment] = arr[j]; } arr[j+increment] = k; } } } }
全部代码：
#include <stdio.h> #include <stdlib.h> #include <time.h> int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5}; int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9}; int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0}; void copy(int *from,int *arr,int length); void print(int *arr,int length); void shellSort(int *arr,int length); int main(){ clock_t start,end; int Arr[10]; int i; copy(arrtest1,Arr,10); print(Arr,10); shellSort(Arr,10); print(Arr,10); start = clock(); for(i=0;i<100000;i++){ copy(arrtest1,Arr,10); //print(Arr,10); shellSort(Arr,10); //print(Arr,10); } end = clock(); printf("first test:%d\n",end-start); start = clock(); for(i=0;i<100000;i++){ copy(arrtest2,Arr,10); //print(Arr,10); shellSort(Arr,10); //print(Arr,10); } end = clock(); printf("first test:%d\n",end-start); start = clock(); for(i=0;i<100000;i++){ copy(arrtest3,Arr,10); //print(Arr,10); shellSort(Arr,10); //print(Arr,10); } end = clock(); printf("first test:%d\n",end-start); getchar(); return 0; } void shellSort(int *arr,int length){ int i,j,k; int increment = length; while(increment>0){ if(increment != 1) increment = increment/3+1; else break; for(i = increment; i<length; i++){ if(arr[i] < arr[i-increment]){ k = arr[i]; for(j=i-increment; j>=0 && k < arr[j] ; j-=increment){ arr[j+increment] = arr[j]; } arr[j+increment] = k; } } } } void copy(int *from,int *arr,int length){ int i; for(i=0;i<length;i++){ arr[i] = from[i]; } } void print(int *arr,int length){ int i; for(i=0;i<length;i++){ printf("%d ",arr[i]); } printf("\n"); }
运行示例：
本文转自博客园xingoo的博客，原文链接：希尔排序，如需转载请自行联系原博主。
