MyMSDN

MyMSDN记录开发新知道

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

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

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

#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函数:按递增顺序对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。

posted on 2008-08-17 04:05 volnet 阅读(8818) 评论(4)  编辑 收藏 引用

评论

# re: 希尔排序(Shell sort)排序算法 2008-08-17 12:04 u2usoft

图片看不到  回复  更多评论   

# re: 希尔排序(Shell sort)排序算法 2008-08-17 17:37 dell笔记本

虽然很古老,但是很经典。  回复  更多评论   

# re: 希尔排序(Shell sort)排序算法 2008-08-17 18:47 踏雪赤兔

始终未弄明白为什么这么多人对shell排序感兴趣~~正如没弄明白为什么这么多人对冒泡排序感兴趣一样……  回复  更多评论   

# re: 希尔排序(Shell sort)排序算法[未登录] 2008-08-17 19:27 niino

冒泡排序的名字是如何来的呢...
  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


特殊功能