希尔排序

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

排序

基本思想

　　希尔排序基本思想：

　　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

　　该方法实质上是一种分组插入方法。

　　给定实例的shell排序的排序过程

　　假设待排序文件有10个记录，其关键字分别是：

　　49，38，65，97，76，13，27，49，55，04。

　　增量序列的取值依次为：

　　5，3，1

Shell排序

　　Shell排序的算法实现:

　　1． 不设监视哨的算法描述

　　void ShellPass(SeqList R，int d)

　　{//希尔排序中的一趟排序，d为当前增量

　　for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区

　　if(R[ i ].key<R[i-d].key){

　　R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵

　　do {//查找R的插入位置

　　R[j+d]=R[j]； //后移记录

　　j=j-d； //查找前一记录

　　}while(j>0&&R[0].key<R[j].key)；

　　R[j+d]=R[0]； //插入R到正确的位置上

　　} //endif

　　} //ShellPass

　　void ShellSort(SeqList R)

　　{

　　int increment=n； //增量初值，不妨设n>0

　　do {

　　increment=increment/3+1； //求下一增量

　　ShellPass(R，increment)； //一趟增量为increment的Shell插入排序

　　}while(increment>1)

　　} //ShellSort

　　注意：

　　当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。

　　2．设监视哨的shell排序算法

　　具体算法【参考书目[12] 】

　　算法分析

　　1．增量序列的选择

　　Shell排序的执行时间依赖于增量序列。

　　好的增量序列的共同特征：

　　① 最后一个增量必须为1；

　　② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

　　有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。

　　2．Shell排序的时间性能优于直接插入排序，据统计分析其时间复杂度为O(n1.3)

　　希尔排序的时间性能优于直接插入排序的原因：

　　①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

　　②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。

　　③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

　　因此，希尔排序在效率上较直接插人排序有较大的改进。

　　3．稳定性

　　希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。

选择排序

　　选择排序的基本思想是：

　　对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。

　　例1:输入序列数据按非减顺序输出.

　　程序如下:

　　program xzpx;

　　const n=7;

　　var a:array[1..n] of integer;

　　i,j,k,t:integer;

　　begin

　　write('Enter date:');

　　for i:= 1 to n do read(a[i]);

　　writeln;

　　for i:=1 to n-1 do

　　begin

　　k:=i;

　　for j:=i+1 to n do

　　if a[j]<a[k] then k:=j;

　　if k<>i then

　　begin t:=a;a:=a[k];a[k]:=t;end;

　　end;

　　write('output data:');

　　for i:= 1 to n do write(a:6);

　　writeln;

　　end.

[编辑本段]

希尔排序的JAVA实现

　　public class Test {

　　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 &lt; Index - 1; i++)

　　System.out.printf("%3s ", a[i]);

　　System.out.println("");

　　ShellSort(Index - 1); // 选择排序

　　// 排序后结果

　　System.out.print("排序后: ");

　　for (i = 0; i &lt; Index - 1; 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 &lt; Index; j++) {

　　Change = false;

　　Temp = a[j]; // 暂存Data[j]的值,待交换值时用

　　Pointer = j - DataLength; // 计算进行处理的位置

　　// 进行集合内数值的比较与交换值

　　while (Temp &lt; a[Pointer] && Pointer >= 0 && Pointer &lt;= Index) {

　　a[Pointer + DataLength] = a[Pointer];

　　// 计算下一个欲进行处理的位置

　　Pointer = Pointer - DataLength;

　　Change = true;

　　if (Pointer &lt; 0 || Pointer > Index)

　　break;

　　}

　　// 与最后的数值交换

　　a[Pointer + DataLength] = Temp;

　　if (Change) {

　　// 打印目前排序结果

　　System.out.print("排序中: ");

　　for (k = 0; k &lt; Index; k++)

　　System.out.printf("%3s ", a[k]);

　　System.out.println("");

　　}

　　}

　　DataLength = DataLength / 2; // 计算下次分割的间隔长度

　　}

　　}

　　}

[编辑本段]

希尔排序的C#实现

　　using System;

　　public class ShellSorter

　　{

　　public void Sort(int[] list)

　　{

　　int inc;

　　for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;

　　for (; inc > 0; inc /= 3)

　　{

　　for (int i = inc + 1; i <= list.Length; i += inc)

　　{

　　int t = list[i - 1];

　　int j = i;

　　while ((j > inc) && (list[j - inc - 1] > t))

　　{

　　list[j - 1] = list[j - inc - 1];

　　j -= inc;

　　}

　　list[j - 1] = t;

　　}

　　}

　　}

　　}

　　public class MainClass

　　{

　　public static void Main()

　　{

　　int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };

　　ShellSorter sh = new ShellSorter();

　　sh.Sort(iArrary);

　　for (int m = 0; m <= 13; m++)

　　Console.WriteLine("{0}", iArrary[m]);

　　Console.ReadKey();

　　}

　　}

[编辑本段]

希尔排序的Pascal实现

　　program ShellSorter;

　　const n=7; typearr=array[1..n] of integer;

　　vara:arr;i,j,t,d:integer;

　　bool:boolean;

　　begin

　　write('input data:');

　　for i:=1 to n do read(a[i]);writeln;

　　d:=n;

　　while d>1 do begin d:=d div 2;

　　for j:=d+1 to n do begin t:=a[j];

　　i:=j-d;

　　while (i>0) and (a[i]>t) do

　　begin

　　a[i+d]:=a[i];

　　i:=i-d;

　　end;

　　a[i+d]:=t;

　　end;

　　end;

　　write('output data:');

　　for i:=1 to n do write(a[i]:6);

　　writeln;

　　end.