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 = 4V[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 = 2V[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 = 1V[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
分享到：
相关推荐
Marcin Ciura在“Best Increments for the Average Case of Shellsort”论文中提出了一种新的增量序列，该序列经过分析后，能将希尔排序的平均运行时间降低约3%，并且有理由相信这些序列可能是最优的。 传统上，...
### 希尔排序（Shell Sort）详解 #### 一、引言 希尔排序是一种基于插入排序的高效排序算法，由计算机科学家Donald Shell在1959年提出。该算法通过将原始序列分割成多个子序列，分别进行插入排序来提高排序效率。...
在实现希尔排序时，常见的增量序列有Hibbard序列、Sedgewick序列、Shellsort 3/2序列等。选择不同的序列会影响排序的速度和效果。 希尔排序源代码的关键部分通常包括以下函数： 1. `shell_sort()`：主函数，调用...
binary sort，二分法查找，binary search， 二分法排序，merge sort 混合排序，shell sort 希尔排序，insertion sort 插入排序。数据结构 data structure
// ShellSort 函数实现整个希尔排序过程 void ShellSort(int a[], int length) { int dk, k; for (dk = (length + 1) / 2; dk >= 1; dk /= 2) { // 确定增量序列 ShellInsert(a, dk, length); // 对每个增量进行...
希尔排序(Shell Sort)是由Donald Shell在1959年提出的一种基于插入排序的改进算法。它的主要思想是通过设置一系列的增量序列，逐步减少这些增量，将待排序的元素进行分组，然后在每个小组内进行直接插入排序。这个...
这段代码中，`shellSort`方法实现了希尔排序的核心逻辑，`main`方法则创建了一个测试用例并调用了排序方法。`TestShellSort.java`可能包含了对该排序算法的测试和性能评估，具体实现要看源代码内容。 希尔排序的优...
希尔排序（Shell Sort）是一种插入排序的改进版，由Donald Shell在1959年提出。它是通过将待排序的数据序列划分为多个子序列，然后对每个子序列进行插入排序，逐渐减少子序列的间隔，直到间隔为1，即整个序列成为一...
希尔排序（Shell Sort）是一种基于插入排序的快速排序算法，由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列，然后对每个子序列进行插入排序，最后再进行一次全局的插入...
通常，Java代码会包含一个名为`shellSort()`的函数，它接收一个整数数组作为参数，并对其进行希尔排序。以下是希尔排序的基本步骤： 1. 定义初始间隔`gap`，一般选择序列的第一个值。 2. 对每个子序列`arr[i], arr...
3. **希尔排序（Shell Sort）**： 希尔排序是插入排序的一种优化版本，通过将待排序的元素按某个增量分组，然后对每组进行插入排序，逐渐减少增量，直到增量为1，完成排序。希尔排序的时间复杂度在最坏情况下为O(n^...
在主函数 `main()` 中，程序通过用户输入来确定数组的大小以及每个元素的值，随后调用 `ShellSort` 类的方法完成希尔排序过程，并输出排序后的结果。 #### 希尔排序的效率分析 希尔排序的时间复杂度取决于增量序列...
希尔排序（Shell Sort）是一种基于插入排序的快速排序算法，由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列，然后对每个子序列进行插入排序，最后再进行一次全局的插入...
这个例子中，`insertion_sort`函数实现了插入排序，而`shell_sort`函数则是希尔排序的主体，它通过调用`insertion_sort`处理每个子序列。注意，实际应用中，可能会使用更复杂的增量序列策略来提高效率。 在提供的...
希尔排序（Shell Sort）是一种基于插入排序的快速排序算法，由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列，然后对每个子序列进行插入排序，最后再进行一次全局的插入...
void shellSort(int arr[], int n) { int gap, i, j, temp; for (gap = n / 2; gap > 0; gap /= 2) { for (i = gap; i ; i++) { temp = arr[i]; j = i; while (j >= gap && arr[j - gap] > temp) { arr[j]...
希尔排序（Shell Sort）是一种基于插入排序的高效算法。它通过将原始数组分割成多个子序列来进行排序，从而提高了插入排序的效率。希尔排序的核心思想是通过将相隔某个增量（gap）的元素组成一个子序列进行插入排序...
希尔排序（Shell Sort）是一种基于插入排序的快速排序算法，由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列，然后分别对每个子序列进行插入排序，最后再进行一次全局的...
- **希尔排序**（`shellsort(SeqList L)`）： - 同样先输出原始数组，然后选择一个初始步长（通常是数组长度的一半），并逐渐减小步长直至为1。 - 在每一轮排序中，将相隔步长的元素进行直接插入排序。 - 排序...