Shell排序算法是D.L.Shell于1959年發(fā)明的，其基本思想是：
下面的這段代碼是Shell算法的C語(yǔ)言實(shí)現(xiàn)，其中shellsort為原函數(shù)，而traceShellsort則為跟蹤輸出的函數(shù)，這里我用了幾個(gè)標(biāo)準(zhǔn)輸出的語(yǔ)句，將數(shù)據(jù)交換的過(guò)程進(jìn)行一個(gè)輸出，以更好地理解排序的過(guò)程。
#include <stdio.h>
#include <stdlib.h>
#define ARRAY_LENGTH 9
void shellsort(int v[], int n);
void arrayPrintf(int v[], int n);
void traceShellsort(int v[], int n);
int traceOut(int n, int gap, int i, int j, int isnewline);
int traceCount;
int main(void) {
int arr[ARRAY_LENGTH] = { 12, 2, 20, 19, 28, 30, 12, 42, 35 };
printf("Original array:\t\t");
arrayPrintf(arr, ARRAY_LENGTH);
/*sort the array by shell arithmetic*/
//shellsort(arr, ARRAY_LENGTH);
traceShellsort(arr, ARRAY_LENGTH);
putchar('\n');
printf("MinToMax array:\t\t");
arrayPrintf(arr, ARRAY_LENGTH);
return EXIT_SUCCESS;
}
/*shellsort函數(shù)：按遞增順序?qū)[0]…v[n-1]進(jìn)行排序*/
void shellsort(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;
}
}
/*shell排序算法的跟蹤版，相同的算法，它將輸出帶有跟蹤過(guò)程的數(shù)據(jù)*/
void traceShellsort(int v[], int n) {
int gap, i, j, temp;
extern int traceCount;
traceCount = 1;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
for (j = i - gap; traceOut(n, gap, i, j, !(j >= 0 && v[j] > v[j
+ gap])) && j >= 0 && v[j] > v[j + gap]; j -= gap) {
temp = v[j];
v[j] = v[j + gap];
v[j + gap] = temp;
arrayPrintf(v, n);
}
}
}
}
/*用于跟蹤交換過(guò)程*/
int traceOut(int n, int gap, int i, int j, int isnewline) {
printf("%2d. n=%d gap=%d i=%d j=%2d %c", traceCount++, n, gap, i, j,
isnewline ? '\n' : ' ');
return 1;
}
/*用于輸出一組數(shù)組*/
void arrayPrintf(int v[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", v[i]);
putchar('\n');
}
下面的文字是運(yùn)行上面一段代碼后產(chǎn)生的結(jié)果，其中跟蹤過(guò)程中出現(xiàn)的數(shù)組輸出，表示該數(shù)組步驟中將會(huì)產(chǎn)生一次位置交換過(guò)程。
Original array: 12 2 20 19 28 30 12 42 35
1. n=9 gap=4 i=4 j=0
2. n=9 gap=4 i=5 j=1
3. n=9 gap=4 i=6 j=2 12 2 12 19 28 30 20 42 35
4. n=9 gap=4 i=6 j=-2
5. n=9 gap=4 i=7 j=3
6. n=9 gap=4 i=8 j=4
7. n=9 gap=2 i=2 j=0
8. n=9 gap=2 i=3 j=1
9. n=9 gap=2 i=4 j=2
10. n=9 gap=2 i=5 j=3
11. n=9 gap=2 i=6 j=4 12 2 12 19 20 30 28 42 35
12. n=9 gap=2 i=6 j=2
13. n=9 gap=2 i=7 j=5
14. n=9 gap=2 i=8 j=6
15. n=9 gap=1 i=1 j=0 2 12 12 19 20 30 28 42 35
16. n=9 gap=1 i=1 j=-1
17. n=9 gap=1 i=2 j=1
18. n=9 gap=1 i=3 j=2
19. n=9 gap=1 i=4 j=3
20. n=9 gap=1 i=5 j=4
21. n=9 gap=1 i=6 j=5 2 12 12 19 20 28 30 42 35
22. n=9 gap=1 i=6 j=4
23. n=9 gap=1 i=7 j=6
24. n=9 gap=1 i=8 j=7 2 12 12 19 20 28 30 35 42
25. n=9 gap=1 i=8 j=6
MinToMax array: 2 12 12 19 20 28 30 35 42
為了更好地查看當(dāng)前值，我將每一次交換的值用下劃線進(jìn)行標(biāo)出。
希爾排序(Shell sort)也稱“縮小增量排序”。它的做法不是每次一個(gè)元素挨一個(gè)元素的比較。而是先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。這樣大大減少了記錄移動(dòng)次數(shù)，提高了排序效率。
算法思路：先取一個(gè)正整數(shù)d1（d1＜n），把全部記錄分成d1個(gè)組，所有距離為dl的倍數(shù)的記錄看成是一組，然后在各組內(nèi)進(jìn)行插入排序；接著取d2（d2＜d1），重復(fù)上述分組和排序操作；直到di=1 (i＞＝1)，即所有記錄成為一個(gè)組為止。希爾排序?qū)υ隽啃蛄械倪x擇沒(méi)有嚴(yán)格規(guī)定，一般選d1約為n／2，d2為d1／2，d3為d2／2，…，di＝1。