[C语言] 插入排序之希尔（shell）排序的特性及实现
1、算法特性
希尔排序法又称缩小增量法，由直接插入排序改进而来，是一种不稳定的插入排序方法。其本质上是一种分组排序方法，不需要大量的辅助空间，和归并排序一样容易实现，适合中小规模的数据排序。
其时间复杂度最好情况为O（n）、最差为O（n²）、平均为O（n^1.5），空间复杂度为O（1）。
2、算法思路
希尔排序先是设定了一个增量l（一般初始l=len/2），并通过插入排序将所有相距为l的数据排成有序序列，接着将增量l缩小折半，继续利用插入排序排序。 经过不断循环，当l折半至1时便可以将所有数据排列有序。
3、实现代码
1 #include <stdio.h> 2 3 // 插入排序： shell排序 4 void shell_sort(int a[], int len) 5 { 6 int i,j,l; 7 for(l=len/2; l>0; l/=2) 8 { 9 for(i=l; i<len; i++) 10 { 11 int temp = a[i]; 12 for(j=i; j>=l && a[j-l]>temp; j-=l) 13 a[j] =a [j-l]; 14 a[j] = temp; 15 } 16 } 17 } 18 19 void travel(int arr[],int len) 20 { 21 for(int i=0;i<len;i++) 22 { 23 printf("%d ",arr[i]); 24 } 25 printf("\n"); 26 } 27 28 int main() 29 { 30 int arr[] = {53,82,9,233,43,14,55,9,4,67}; 31 int len = sizeof(arr)/sizeof(arr[0]); 32 33 /* travel(arr,len); 34 insert_sort(arr,len); 35 travel(arr,len);*/ 36 37 /* travel(arr,len); 38 binary_insert_sort(arr,len); 39 travel(arr,len);*/ 40 41 travel(arr,len); 42 shell_sort(arr,len); 43 travel(arr,len); 44 45 return 0; 46 }
4、实现效果
