shell(希尔)排序（改良的插入排序）

说明

插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速度不快。

排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加

快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。

解法

Shell排序法最初是D.LShell于1959所提出，假设要排序的元素有n个，则每次进行插入排序时

并不是所有的元素同时进行时，而是取一段间隔。

Shell首先将间隔设定为n/2，然后跳跃进行插入排序，再来将间隔n/4，跳跃进行排序动作，再来

间隔设定为n/8、n/16，直到间隔为1之后的最 后一次排序终止，由于上一次的排序动作都会将

固定间隔内的元素排序好，所以当间隔越来越小时，某些元素位于正确位置的机率越高，因此

最后几次的排序动作将 可以大幅减低。

举个例子来说，假设有一未排序的数字如右：89 12 65 97 61 81 27 2 61 98

数字的总数共有10个，所以第一次我们将间隔设定为10 / 2 = 5，此时我们对间隔为5的数字进行

排序，如下所示：

画线连结的部份表示 要一起进行排序的部份，再来将间隔设定为5 / 2的商，也就是2，则第二

次的插入排序对象如下所示：

再来间隔设定为2 / 2 = 1，此时就是单纯的插入排序了，由于大部份的元素都已大致排序过了，

所以最后一次的插入排序几乎没作什么排序动作了:

#include <stdio.h>
#include <stdlib.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void shellsort(int[]);
int main(void)
{
int number[MAX] = {0};
int i;
srand(time(NULL));
printf("排序前：");
for(i = 0; i < MAX; i++)
{
number[i] = rand() % 100;
printf("%d ", number[i]);
}
shellsort(number);
return 0;
}
void shellsort(int number[])
{
int i, j, k, gap, t;
gap = MAX / 2;
while(gap > 0)
{
for(k = 0; k < gap; k++)
{
for(i = k+gap; i < MAX; i+=gap)
{
for(j = i - gap; j >= k; j-=gap)
{
if(number[j] > number[j+gap])
{
SWAP(number[j], number[j+gap]);
}
else
break;
}
}
}
printf("\ngap = %d：", gap);
for(i = 0; i < MAX; i++)
printf("%d ", number[i]);
printf("\n");
gap /= 2;
}
}

//测试结果

java实现

public class ShellTest {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };

public static void main(String args[]) {
int i; // 循环计数变量
int index = a.length; // 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < index; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
shellSort(index); // 选择排序

System.out.print("排序后: "); // 排序后结果
for (i = 0; i < index; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
}

public static void shellSort(int index) {
int i, j, k; // 循环计数变量
int temp; // 暂存变量
boolean change; // 数据是否改变
int dataLength; // 分割集合的间隔长度
int pointer; // 进行处理的位置
dataLength = (int) index / 2; // 初始集合间隔长度
while (dataLength > 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = dataLength; j < index; j++) {
change = false;
temp = a[j]; // 暂存Data[j]的值,待交换值时用
pointer = j - dataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
//while (temp < a[pointer] && pointer >= 0 && pointer <= index) {

while (temp < a[pointer]) {
a[pointer + dataLength] = a[pointer];
// 计算下一个欲进行处理的位置
pointer = pointer - dataLength;
change = true;
if (pointer < 0 || pointer > index)
break;
}
// 与最后的数值交换
a[pointer + dataLength] = temp;
if (change) {
// 打印排序结果
System.out.print("排序中: ");
for (k = 0; k < index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
dataLength = dataLength / 2; // 计算下次分割的间隔长度
}
}
}