Shell排序算法是D.L.Shell于1959年發(fā)明的，其基本思想是：
下面的這段代碼是Shell算法的C語言實現(xiàn)，其中shellsort為原函數(shù)，而traceShellsort則為跟蹤輸出的函數(shù)，這里我用了幾個標準輸出的語句，將數(shù)據(jù)交換的過程進行一個輸出，以更好地理解排序的過程。
#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ù)：按遞增順序對v[0]…v[n-1]進行排序*/
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排序算法的跟蹤版，相同的算法，它將輸出帶有跟蹤過程的數(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);
}
}
}
}
/*用于跟蹤交換過程*/
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');
}
下面的文字是運行上面一段代碼后產生的結果，其中跟蹤過程中出現(xiàn)的數(shù)組輸出，表示該數(shù)組步驟中將會產生一次位置交換過程。
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
為了更好地查看當前值，我將每一次交換的值用下劃線進行標出。
希爾排序(Shell sort)也稱“縮小增量排序”。它的做法不是每次一個元素挨一個元素的比較。而是先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插入排序。這樣大大減少了記錄移動次數(shù)，提高了排序效率。
算法思路：先取一個正整數(shù)d1（d1＜n），把全部記錄分成d1個組，所有距離為dl的倍數(shù)的記錄看成是一組，然后在各組內進行插入排序；接著取d2（d2＜d1），重復上述分組和排序操作；直到di=1 (i＞＝1)，即所有記錄成為一個組為止。希爾排序對增量序列的選擇沒有嚴格規(guī)定，一般選d1約為n／2，d2為d1／2，d3為d2／2，…，di＝1。