Shell Sort 希尔排序 收藏
Shell Sort 希爾排序 收藏
希爾排序（Shell Sort）又叫做縮小增量排序（diminishing increment sort），是一種很優秀的排序法，算法本身不難理解，也很容易實現，而且它的速度很快。
插入排序（Insertion Sort）的一個重要的特點是，如果原始數據的大部分元素已經排序，那么插入排序的速度很快（因為需要移動的元素很少）。從這個事實我們可以想到，如果原始數據只有很少元素，那么排序的速度也很快。－－希爾排序就是基于這兩點對插入排序作出了改進。
例如，有100個整數需要排序。
第一趟排序先把它分成50組，每組2個整數，分別排序。
第二趟排序再把經過第一趟排序后的100個整數分成25組，每組4個整數，分別排序。
第三趟排序再把前一次排序后的數分成12組，第組8個整數，分別排序。
照這樣子分下去，最后一趟分成100組，每組一個整數，這就相當于一次插入排序。
由于開始時每組只有很少整數，所以排序很快。之后每組含有的整數越來越多，但是由于這些數也越來越有序，所以排序速度也很快。
下面用C語言實現希爾排序，用的是K&R里的算法，該算法結構很清晰。
/* [K&R] p.62 section 3.5 */
void shellsort2(int V[], int n)
{
? int gap, i, j, temp;
? for (gap = n/2; gap > 0; gap /= 2)
??? for (i = gap; i < n; i++)
????? for (j = i-gap; j>=0 && V[j]>V[j+gap]; j -= gap) {
?temp = V[j];
?V[j] = V[j+gap];
?V[j+gap] = temp;
????? }
}
由于嵌套了三個循環語句，邏輯上比較復雜，為了看清楚希爾排序的細節，我在這些循環中間加入一些 printf() 語句：
/* kikistar.com - 加入了多個 printf() 的 Shell Sort 程序，以便看清排序步驟 */
#include <stdio.h>
#include <stdlib.h>
#define MAX 8
void shellsort(int A[], int N);
void printarray(int A[]);
int main()
{
? int i, s[MAX];
? for (i = 0; i < MAX; i++)
??? s[i] = 1+(int) (100.0*rand()/(RAND_MAX+1.0));
? printf("before?? :");??// 打印排序前的數據
? printarray(s);
? shellsort(s, MAX);
? return 0;
}
/* [K&R] p.62 section 3.5 */
void shellsort(int V[], int n)
{
? int gap, i, j, temp;
? for (gap = n/2; gap > 0; gap /= 2) {
??? printf("/ngap = %d/t/tV[j] - V[j+gap]/n", gap);?//打印gap的值
??? for (i = gap; i < n; i++) {
????? printf("i = %d/t/t", i);????//打印 i 的值
????? for (j = i-gap; j>=0; j -= gap) {
?if (V[j] > V[j+gap]) {
?? temp = V[j];
?? V[j] = V[j+gap];
?? V[j+gap] = temp;
?}
?printf("[%2d]-[%2d]? ", j, j+gap);?//打印每次進行比較的 j 和 j+gap
????? }
????? printf("/n");
??? }
??? printf("after gap(%d):", gap);??//打印每趟排序后的結果
??? printarray(V);
? }
}
void printarray(int a[])
{
? int i;
? for (i = 0; i < MAX; i++)
??? printf(" %d", a[i]);
? printf("/n");
}
運行該程序，有如下輸出：
其中，[ 0]-[ 4] 的意思是 V[0]與V[4]進行比較。這要就可以看清楚希爾排序的每一個步驟了。
before?? : 85 40 79 80 92 20 34 77
gap = 4?V[j] - V[j+gap]
i = 4?[ 0]-[ 4]?
i = 5?[ 1]-[ 5]?
i = 6?[ 2]-[ 6]?
i = 7?[ 3]-[ 7]?
after gap(4): 85 20 34 77 92 40 79 80
gap = 2?V[j] - V[j+gap]
i = 2?[ 0]-[ 2]?
i = 3?[ 1]-[ 3]?
i = 4?[ 2]-[ 4]? [ 0]-[ 2]?
i = 5?[ 3]-[ 5]? [ 1]-[ 3]?
i = 6?[ 4]-[ 6]? [ 2]-[ 4]? [ 0]-[ 2]?
i = 7?[ 5]-[ 7]? [ 3]-[ 5]? [ 1]-[ 3]?
after gap(2): 34 20 79 40 85 77 92 80
gap = 1?V[j] - V[j+gap]
i = 1?[ 0]-[ 1]?
i = 2?[ 1]-[ 2]? [ 0]-[ 1]?
i = 3?[ 2]-[ 3]? [ 1]-[ 2]? [ 0]-[ 1]?
i = 4?[ 3]-[ 4]? [ 2]-[ 3]? [ 1]-[ 2]? [ 0]-[ 1]?
i = 5?[ 4]-[ 5]? [ 3]-[ 4]? [ 2]-[ 3]? [ 1]-[ 2]? [ 0]-[ 1]?
i = 6?[ 5]-[ 6]? [ 4]-[ 5]? [ 3]-[ 4]? [ 2]-[ 3]? [ 1]-[ 2]? [ 0]-[ 1]?
i = 7?[ 6]-[ 7]? [ 5]-[ 6]? [ 4]-[ 5]? [ 3]-[ 4]? [ 2]-[ 3]? [ 1]-[ 2]? [ 0]-[ 1]?
after gap(1): 20 34 40 77 79 80 85 92
具體地，第一趟排序把這8個數分成4組，每組2個元素，分別是 {V[0], V[4]}, {V[1], V[5]}, {V[2], V[6]}, {V[3], V[7]}。第二趟實質上是分了兩組，第組4個數，分別是 {V[0], V[2], V[4], V[6]} 和 {V[1], V[3], V[5], V[7]}。最后一趟就相當于一次插入排序了。
上文提及，由于開始時每組只有很少整數，所以排序很快。之后每組含有的整數越來越多，但是由于這些數也越來越有序，所以排序速度也很快。
然而情況并不總是這么理想的，在一些特定（但并不算罕見）的情況下，雖然經過了很多趟排序但是數據卻沒有變得更有序。例如，如果用上面的算法對下面這些數進行排序
1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16會得到以下結果：
after gap(8): 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16
after gap(4): 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16
after gap(2): 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16
after gap(1): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
在 gap=1 之前的每一趟排序都在浪費時間！
這種壞情形是可以避免的，方法是在你的房間或辦公室的東南方位放置一個金魚缸，注意里面的金魚數目一定要是素數。有一個更簡單的方法，就是把上面的增量數列（1, 2, 4, 8）改成Hibbard增量（1, 3, 5, 7）。
由此可見，增量數列的選擇對希爾排序的性能有著極大的影響。[Mark Allen Weiss]指出，最好的增量序列是 Sedgewick提出的 (1, 5, 19, 41, 109,...)，該序列的項來自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 這兩個算式。
下面是一個使用 Sedgewick增量 的希爾排序的完整C語言程序：
/* kikistar.com - 使用 Sedgewick增量 的 Shell Sort 程序 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 1000000?//這里設定要對多少個元素排序
void shellsort(int A[], int N, int *);
void printarray(int A[]);
int main()
{
? int i, s[MAX];
? int *sed;
? int sedgewick[] = {??// Sedgewick增量
??? 1073643521, 603906049, 268386305, 150958081, 67084289,
??? 37730305, 16764929, 9427969, 4188161, 2354689,
??? 1045505, 587521, 260609, 146305, 64769,
??? 36289, 16001, 8929, 3905, 2161,
??? 929, 505, 209, 109, 41,
??? 19, 5, 1, 0 };??//用 0 標記終點
? for (sed = sedgewick; *sed > MAX; sed++)?// 增量必須小于元素個數
??? /* void */;
? for (i = 0; i < MAX; i++)
??? s[i] = 1+(int) ((float)MAX*rand()/(RAND_MAX+1.0));
? printf("before?? :");
? printarray(s);
? shellsort(s, MAX, sed);
? printf("after??? :");
? printarray(s);
? return 0;
}
/* Shell Sort: 把增量序列放在數組里 */
void shellsort(int v[], int n, int *sed)
{
? int i, j, temp;
? int *gap;
? for (gap = sed; *gap > 0; gap++)
??? for (i = *gap; i < n; i++)
????? for (j = i - *gap; j>=0 && v[j]>v[j + *gap]; j -= *gap) {
?temp = v[j];
?v[j] = v[j + *gap];
?v[j + *gap] = temp;
????? }
}
void printarray(int a[])
{
? int i;
? for (i = 0; i < MAX; i++)
??? printf(" %d", a[i]);
? printf("/n");
}
在Linux下可以這樣測試程序的運行時間：
$ time ./a.out >/dev/null
real??? 0m2.603s
user??? 0m2.549s
sys???? 0m0.019s
上面是在我的機器里，把 MAX 設定為 1000000 時的運行時間。
Sedgewick增量可用像下面那樣的程序求得。
/* 計算 Sedgewick增量 的程序 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define wick? 100
void insertsort(int A[], int N);
void printarray(int A[], int from, int to);
int main()
{
? int i, j;
? int sedge[wick];
? i = -1;
? do {
??? ++i;
??? sedge[i] = 9 * pow(4,i) - 9 * pow(2,i) + 1;
??? printf("sedge[%d] = %d/n", i, sedge[i]);
? } while (sedge[i] > 0);
? printf("/n");
? j = 1;
? do {
??? ++j;?// j = 0 和 j = 1 時該算式的解小于0，所以從 j = 2 開始取值。
??? sedge[j+i-2] = pow(4,j) - 3 * pow(2, j) + 1;
??? printf("sedge[%d] = %d/n", j+i-2, sedge[j+i-2]);
? } while (sedge[j+i-2] > 0);
? printf("/n");
? printarray(sedge, 0, j+i-2);
? insertsort(sedge, j+i-2);
? printarray(sedge, 0, j+i-2);
? return 0;
}
void printarray(int a[], int from, int to)
{
? int i;
? for (i = from; i < to; i++)
??? printf("%d, ", a[i]);
? printf("/n/n");
}
/* 從大到小排序 */
void insertsort(int A[], int n)
{
? int? i, j, key;
? for (j = 1; j < n; j++)
??? {
????? key = A[j];
????? i = j - 1;
????? while (i >= 0 && A[i] < key)
?{
?? A[i+1] = A[i];
?? --i;
?}
????? A[i+1] = key;
??? }
}
由于用了 math.h，用 GCC 編譯時注意要加上 -lm 參數。
$ gcc -Wall sedgewick.c -lm參考資料：
[Mark Allen Weiss] Data Structures and Algorithm Analysis in C (second edition) 中文版 ISBN 7-111-12748-X
[K&R] The C Programming Language (second edition) 影印版 ISBN 7-302-02412-X/TP.1214
發表于 @ 2009年08月08日 10:19:00 | 評論( 0 ) | 編輯| 舉報| 收藏
舊一篇:double 和 long double | 新一篇:產生隨機數
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/liujiejesse/archive/2009/08/09/4424888.aspx
總結
以上是生活随笔為你收集整理的Shell Sort 希尔排序 收藏的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 网站特效-------旋转的图片
- 下一篇： 我看UNIX与Windows的本质区别