希尔排序(Shell sort)排序算法

希尔排序(Shell sort)排序算法

Shell排序算法是D.L.Shell于1959年发明的，其基本思想是：

下面的这段代码是Shell算法的C语言实现，其中shellsort为原函数，而traceShellsort则为跟踪输出的函数，这里我用了几个标准输出的语句，将数据交换的过程进行一个输出，以更好地理解排序的过程。

#include 
#include 
#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函数：按递增顺序对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排序算法的跟踪版，相同的算法，它将输出带有跟踪过程的数据*/
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;
}
/*用于输出一组数组*/
void arrayPrintf(int v[], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", v[i]);
putchar('\n');
}

下面的文字是运行上面一段代码后产生的结果，其中跟踪过程中出现的数组输出，表示该数组步骤中将会产生一次位置交换过程。

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)也称“缩小增量排序”。它的做法不是每次一个元素挨一个元素的比较。而是先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个 序列中的记录基本有序时，再对全体记录进行一次直接插入排序。这样大大减少了记录移动次数，提高了排序效率。
算法思路：先取一个正整数 d1（d1＜n），把全部记录分成d1个组，所有距离为dl的倍数的记录看成是一组，然后在各组内进行插入排序；接着取d2（d2＜d1），重复上述分组 和排序操作；直到di=1 (i＞＝1)，即所有记录成为一个组为止。希尔排序对增量序列的选择没有严格规定，一般选d1约为n／2，d2为d1／2，d3为 d2／2，…，di＝1。