首页 > 代码库 > 希尔排序
希尔排序
希尔排序（Shellsort）的名称源于它的发明者Donald Shell，该算法是冲破二次时间屏障的第一批算法之一。不过，自从它最初被发现，又过了若干年才证明了它的亚二次时间界。
它通过比较相距一定间隔的元素来工作；各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。希尔排序使用一个序列h1，h2，…，ht，叫做增量序列。只要h1=1，任何增量序列都是可行的。在使用增量hk的一趟排序后，对于每一个i我们有A[i] <= A[i+hk]，即所有相隔hk的元素都被排序，此时称序列是hk-排序。希尔排序的一个重要性质是，一个hk-排序的序列在后面排序中保持它的hk排序性。
增量序列的一种流行的选择是使用Shell建议的：ht = N/2和hk = hk+1/2。下面采用该序列进行希尔排序。
1 #include <stdio.h> 2 3 #define ElementType int 4 5 void PrintArray(ElementType A[], int N) 6 { 7 int i; 8 for (i = 0; i < N; i++) 9 {10 printf("%d ", A[i]);11 }12 printf("\n");13 }14 15 void ShellSort(ElementType A[], int N)16 {17 int i, j, Increment;18 ElementType Tmp;19 20 //增量序列为N/221 for (Increment = N/2; Increment > 0; Increment /= 2)22 {23 //从Increment开始排序24 for (i = Increment; i < N; i++)25 {26 //对每个子序列进行插入排序27 Tmp = A[i];28 for (j = i; j >= Increment; j -= Increment)29 {30 if (Tmp < A[j-Increment])31 A[j] = A[j-Increment];32 else33 break;34 }35 A[j] = Tmp;36 }37 printf("%d-sort: ", Increment);38 PrintArray(A, N);39 }40 }41 42 int main()43 {44 int i, N;45 scanf("%d", &N);46 int A[N];47 for (i = 0; i < N; i++)48 {49 scanf("%d", &A[i]);50 }51 52 ShellSort(A, N);53 54 return 0;55 }
希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。