Java经典排序算法之希尔排序详解

Java经典排序算法之希尔排序详解

一、希尔排序(Shell Sort)

希尔排序（Shell Sort）是一种插入排序算法，因D.L.Shell于1959年提出而得名。

Shell排序又称作缩小增量排序。

二、希尔排序的基本思想

希尔排序的中心思想就是：将数据进行分组，然后对每一组数据进行排序，在每一组数据都有序之后，就可以对所有的分组利用插入排序进行最后一次排序。这样可以显著减少交换的次数，以达到加快排序速度的目的。

希尔排序的中心思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2

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

shell排序的算法实现:

void ShellPass(SeqList R，int d)

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

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

if(R[i].key

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

do {//查找R[i]的插入位置

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

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

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

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

} //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"，以防下标越界。

三、希尔排序算法分析

1、增量序列的选择。

Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：

a.最后一个增量必须为1。

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

有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。

2、Shell排序的时间性能优于直接插入排序。

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

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

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

c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

3、稳定性

希尔排序是不稳定的。

四、算法演练

假定待排序文件由10个记录，其关键字分别是：40、38、65、97、76、13、27、49、55、04。

增量序列取值依次为：5、3、1

排序过程演示如下图所示：

其动画效果如下面的gif动画所示：

ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练

希尔排序动画演示

五、代码实现

public class ShellSortTest {

private static void shellSort(int[] source) {

int j;

for (int gap = source.length / 2; gap > 0; gap /= 2) {

for (int i = gap; i < source.length; i++) {

int temp = source[i];

for (j = i; j >= gap && temp < source[j - gap]; j -= gap)

source[j] = source[j - gap];

source[j] = temp;

}

System.out.print("增长序列：" + gap + " :");

printArray(source);

}

}

private static void printArray(int[] source) {

for (int i = 0; i < source.length; i++) {

System.out.print("\t" + source[i]);

}

System.out.println();

}

public static void main(String[] args) {

int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 };

System.out.print("原始序列：");

printArray(source);

System.out.println("");

shellSort(source);

System.out.print("\n\n最后结果：");

printArray(source);

}

}

运行结果为：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：2 : 4 27 13 49 38 55 49 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

发现增长序列是5,2,1  和题目要求的5,3,1不同。通过分析要排序的文件由10个记录，10/2=5,5-2=3,3-2=1。刚好符合要求，因此将上面的代码稍作修改即可改变增长序列的值。

将shellSort(int[] source) 方法里的下面这行代码

for (int gap = source.length / 2; gap > 0; gap /= 2) { 

改为：

for (int gap = source.length / 2; gap > 0; gap -= 2) { 

然后重新运行程序，打印结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：3 : 13 4 49 38 27 49 55 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

如果想使用指定的增长序列来对指定的数组进行希尔排序，可以对上面的程序修改，修改后代码如下：

public class ShellSortTest2 {

/**

* 待排序的数组

*/

private int[] sources;

/**

* 数组内元素个数

*/

private int itemsNum;

/**

* 增量数组序列

*/

private int[] intervalSequence;

/**

* @param maxItems

* 数组大小

* @param intervalSequence

* 增量数组序列

*/

public ShellSortTest2(int[] source, int[] intervalSequence) {

this.sources = new int[source.length];

this.itemsNum = 0;// 还没有元素

this.intervalSequence = intervalSequence;

}

/**

* 希尔排序算法

*/

public void shellSort() {

int gap = 0;// 为增量

for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外层循环，由增量序列元素个数决定

{

gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列

int innerArraySize;// 每次内部插入排序的元素个数

if (0 == itemsNum % gap) {

innerArraySize = itemsNum / gap;

} else {

innerArraySize = itemsNum / gap + 1;

}

for (int i = 0; i < gap; i++) {

int temp = 0;

int out = 0, in = 0;

if (i + (innerArraySize - 1) * gap >= itemsNum) {

innerArraySize--;

}

// 内部用插入排序

for (int j = 1; j < innerArraySize; j++) {

out = i + j * gap;

temp = sources[out];

in = out;

while (in > gap - 1 && sources[in - gap] > temp) {

sources[in] = sources[in - gap];

in = in - gap;

}

sources[in] = temp;

}

}

System.out.print("增长序列为: " + gap + " ");

this.displayArray()ylivUFurlT;

}

}

/**

* 初始化待排序数组

*/

public void initArray(int[] array) {

for (int i = 0; i < array.length; i++) {

sources[i] = array[i];

}

itemsNum = array.length;

}

/**

* 显示数组内容

*/

public void displayArray() {

for (int i = 0; i < itemsNum; i++) {

System.out.print("\t" + sources[i] + " ");

}

System.out.println("\n");

}

public static void main(String[] args) {

int[] intervalSequence = { 5, 3, 1 };

int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };

ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);

// 初始化待排序数组

ss.initArray(source);

System.out.print("原始序列： ");

ss.displayArray();

// 希尔排序

ss.shellSort();

System.out.print("最后结果： ");

ss.displayArray();

}

}

运行结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列为: 5 13 27 49 55 4 49 38 65 97 76

增长序列为: 3 13 4 49 38 27 49 55 65 97 76

增长序列为: 1 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

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

shell排序的算法实现:

void ShellPass(SeqList R，int d)

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

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

if(R[i].key

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

do {//查找R[i]的插入位置

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

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

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

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

} //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"，以防下标越界。

三、希尔排序算法分析

1、增量序列的选择。

Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：

a.最后一个增量必须为1。

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

有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。

2、Shell排序的时间性能优于直接插入排序。

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

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

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

c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

3、稳定性

希尔排序是不稳定的。

四、算法演练

假定待排序文件由10个记录，其关键字分别是：40、38、65、97、76、13、27、49、55、04。

增量序列取值依次为：5、3、1

排序过程演示如下图所示：

其动画效果如下面的gif动画所示：

ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练

希尔排序动画演示

五、代码实现

public class ShellSortTest {

private static void shellSort(int[] source) {

int j;

for (int gap = source.length / 2; gap > 0; gap /= 2) {

for (int i = gap; i < source.length; i++) {

int temp = source[i];

for (j = i; j >= gap && temp < source[j - gap]; j -= gap)

source[j] = source[j - gap];

source[j] = temp;

}

System.out.print("增长序列：" + gap + " :");

printArray(source);

}

}

private static void printArray(int[] source) {

for (int i = 0; i < source.length; i++) {

System.out.print("\t" + source[i]);

}

System.out.println();

}

public static void main(String[] args) {

int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 };

System.out.print("原始序列：");

printArray(source);

System.out.println("");

shellSort(source);

System.out.print("\n\n最后结果：");

printArray(source);

}

}

运行结果为：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：2 : 4 27 13 49 38 55 49 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

发现增长序列是5,2,1  和题目要求的5,3,1不同。通过分析要排序的文件由10个记录，10/2=5,5-2=3,3-2=1。刚好符合要求，因此将上面的代码稍作修改即可改变增长序列的值。

将shellSort(int[] source) 方法里的下面这行代码

for (int gap = source.length / 2; gap > 0; gap /= 2) { 

改为：

for (int gap = source.length / 2; gap > 0; gap -= 2) { 

然后重新运行程序，打印结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：3 : 13 4 49 38 27 49 55 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

如果想使用指定的增长序列来对指定的数组进行希尔排序，可以对上面的程序修改，修改后代码如下：

public class ShellSortTest2 {

/**

* 待排序的数组

*/

private int[] sources;

/**

* 数组内元素个数

*/

private int itemsNum;

/**

* 增量数组序列

*/

private int[] intervalSequence;

/**

* @param maxItems

* 数组大小

* @param intervalSequence

* 增量数组序列

*/

public ShellSortTest2(int[] source, int[] intervalSequence) {

this.sources = new int[source.length];

this.itemsNum = 0;// 还没有元素

this.intervalSequence = intervalSequence;

}

/**

* 希尔排序算法

*/

public void shellSort() {

int gap = 0;// 为增量

for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外层循环，由增量序列元素个数决定

{

gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列

int innerArraySize;// 每次内部插入排序的元素个数

if (0 == itemsNum % gap) {

innerArraySize = itemsNum / gap;

} else {

innerArraySize = itemsNum / gap + 1;

}

for (int i = 0; i < gap; i++) {

int temp = 0;

int out = 0, in = 0;

if (i + (innerArraySize - 1) * gap >= itemsNum) {

innerArraySize--;

}

// 内部用插入排序

for (int j = 1; j < innerArraySize; j++) {

out = i + j * gap;

temp = sources[out];

in = out;

while (in > gap - 1 && sources[in - gap] > temp) {

sources[in] = sources[in - gap];

in = in - gap;

}

sources[in] = temp;

}

}

System.out.print("增长序列为: " + gap + " ");

this.displayArray()ylivUFurlT;

}

}

/**

* 初始化待排序数组

*/

public void initArray(int[] array) {

for (int i = 0; i < array.length; i++) {

sources[i] = array[i];

}

itemsNum = array.length;

}

/**

* 显示数组内容

*/

public void displayArray() {

for (int i = 0; i < itemsNum; i++) {

System.out.print("\t" + sources[i] + " ");

}

System.out.println("\n");

}

public static void main(String[] args) {

int[] intervalSequence = { 5, 3, 1 };

int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };

ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);

// 初始化待排序数组

ss.initArray(source);

System.out.print("原始序列： ");

ss.displayArray();

// 希尔排序

ss.shellSort();

System.out.print("最后结果： ");

ss.displayArray();

}

}

运行结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列为: 5 13 27 49 55 4 49 38 65 97 76

增长序列为: 3 13 4 49 38 27 49 55 65 97 76

增长序列为: 1 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

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

do {//查找R[i]的插入位置

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

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

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

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

} //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"，以防下标越界。

三、希尔排序算法分析

1、增量序列的选择。

Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：

a.最后一个增量必须为1。

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

有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。

2、Shell排序的时间性能优于直接插入排序。

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

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

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

c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

3、稳定性

希尔排序是不稳定的。

四、算法演练

假定待排序文件由10个记录，其关键字分别是：40、38、65、97、76、13、27、49、55、04。

增量序列取值依次为：5、3、1

排序过程演示如下图所示：

其动画效果如下面的gif动画所示：

ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练

希尔排序动画演示

五、代码实现

public class ShellSortTest {

private static void shellSort(int[] source) {

int j;

for (int gap = source.length / 2; gap > 0; gap /= 2) {

for (int i = gap; i < source.length; i++) {

int temp = source[i];

for (j = i; j >= gap && temp < source[j - gap]; j -= gap)

source[j] = source[j - gap];

source[j] = temp;

}

System.out.print("增长序列：" + gap + " :");

printArray(source);

}

}

private static void printArray(int[] source) {

for (int i = 0; i < source.length; i++) {

System.out.print("\t" + source[i]);

}

System.out.println();

}

public static void main(String[] args) {

int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 };

System.out.print("原始序列：");

printArray(source);

System.out.println("");

shellSort(source);

System.out.print("\n\n最后结果：");

printArray(source);

}

}

运行结果为：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：2 : 4 27 13 49 38 55 49 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

发现增长序列是5,2,1  和题目要求的5,3,1不同。通过分析要排序的文件由10个记录，10/2=5,5-2=3,3-2=1。刚好符合要求，因此将上面的代码稍作修改即可改变增长序列的值。

将shellSort(int[] source) 方法里的下面这行代码

for (int gap = source.length / 2; gap > 0; gap /= 2) { 

改为：

for (int gap = source.length / 2; gap > 0; gap -= 2) { 

然后重新运行程序，打印结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：3 : 13 4 49 38 27 49 55 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

如果想使用指定的增长序列来对指定的数组进行希尔排序，可以对上面的程序修改，修改后代码如下：

public class ShellSortTest2 {

/**

* 待排序的数组

*/

private int[] sources;

/**

* 数组内元素个数

*/

private int itemsNum;

/**

* 增量数组序列

*/

private int[] intervalSequence;

/**

* @param maxItems

* 数组大小

* @param intervalSequence

* 增量数组序列

*/

public ShellSortTest2(int[] source, int[] intervalSequence) {

this.sources = new int[source.length];

this.itemsNum = 0;// 还没有元素

this.intervalSequence = intervalSequence;

}

/**

* 希尔排序算法

*/

public void shellSort() {

int gap = 0;// 为增量

for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外层循环，由增量序列元素个数决定

{

gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列

int innerArraySize;// 每次内部插入排序的元素个数

if (0 == itemsNum % gap) {

innerArraySize = itemsNum / gap;

} else {

innerArraySize = itemsNum / gap + 1;

}

for (int i = 0; i < gap; i++) {

int temp = 0;

int out = 0, in = 0;

if (i + (innerArraySize - 1) * gap >= itemsNum) {

innerArraySize--;

}

// 内部用插入排序

for (int j = 1; j < innerArraySize; j++) {

out = i + j * gap;

temp = sources[out];

in = out;

while (in > gap - 1 && sources[in - gap] > temp) {

sources[in] = sources[in - gap];

in = in - gap;

}

sources[in] = temp;

}

}

System.out.print("增长序列为: " + gap + " ");

this.displayArray()ylivUFurlT;

}

}

/**

* 初始化待排序数组

*/

public void initArray(int[] array) {

for (int i = 0; i < array.length; i++) {

sources[i] = array[i];

}

itemsNum = array.length;

}

/**

* 显示数组内容

*/

public void displayArray() {

for (int i = 0; i < itemsNum; i++) {

System.out.print("\t" + sources[i] + " ");

}

System.out.println("\n");

}

public static void main(String[] args) {

int[] intervalSequence = { 5, 3, 1 };

int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };

ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);

// 初始化待排序数组

ss.initArray(source);

System.out.print("原始序列： ");

ss.displayArray();

// 希尔排序

ss.shellSort();

System.out.print("最后结果： ");

ss.displayArray();

}

}

运行结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列为: 5 13 27 49 55 4 49 38 65 97 76

增长序列为: 3 13 4 49 38 27 49 55 65 97 76

增长序列为: 1 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

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

} //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"，以防下标越界。

三、希尔排序算法分析

1、增量序列的选择。

Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：

a.最后一个增量必须为1。

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

有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。

2、Shell排序的时间性能优于直接插入排序。

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

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

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

c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

3、稳定性

希尔排序是不稳定的。

四、算法演练

假定待排序文件由10个记录，其关键字分别是：40、38、65、97、76、13、27、49、55、04。

增量序列取值依次为：5、3、1

排序过程演示如下图所示：

其动画效果如下面的gif动画所示：

ps:读者也可以自己打开下面的链接，自己设定要排序的数组，进行排序演练

希尔排序动画演示

五、代码实现

public class ShellSortTest {

private static void shellSort(int[] source) {

int j;

for (int gap = source.length / 2; gap > 0; gap /= 2) {

for (int i = gap; i < source.length; i++) {

int temp = source[i];

for (j = i; j >= gap && temp < source[j - gap]; j -= gap)

source[j] = source[j - gap];

source[j] = temp;

}

System.out.print("增长序列：" + gap + " :");

printArray(source);

}

}

private static void printArray(int[] source) {

for (int i = 0; i < source.length; i++) {

System.out.print("\t" + source[i]);

}

System.out.println();

}

public static void main(String[] args) {

int source[] = new int[] {49,38,65,97,76,13,27,49,55,04 };

System.out.print("原始序列：");

printArray(source);

System.out.println("");

shellSort(source);

System.out.print("\n\n最后结果：");

printArray(source);

}

}

运行结果为：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：2 : 4 27 13 49 38 55 49 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

发现增长序列是5,2,1  和题目要求的5,3,1不同。通过分析要排序的文件由10个记录，10/2=5,5-2=3,3-2=1。刚好符合要求，因此将上面的代码稍作修改即可改变增长序列的值。

将shellSort(int[] source) 方法里的下面这行代码

for (int gap = source.length / 2; gap > 0; gap /= 2) { 

改为：

for (int gap = source.length / 2; gap > 0; gap -= 2) { 

然后重新运行程序，打印结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列：5 : 13 27 49 55 4 49 38 65 97 76

增长序列：3 : 13 4 49 38 27 49 55 65 97 76

增长序列：1 : 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

如果想使用指定的增长序列来对指定的数组进行希尔排序，可以对上面的程序修改，修改后代码如下：

public class ShellSortTest2 {

/**

* 待排序的数组

*/

private int[] sources;

/**

* 数组内元素个数

*/

private int itemsNum;

/**

* 增量数组序列

*/

private int[] intervalSequence;

/**

* @param maxItems

* 数组大小

* @param intervalSequence

* 增量数组序列

*/

public ShellSortTest2(int[] source, int[] intervalSequence) {

this.sources = new int[source.length];

this.itemsNum = 0;// 还没有元素

this.intervalSequence = intervalSequence;

}

/**

* 希尔排序算法

*/

public void shellSort() {

int gap = 0;// 为增量

for (int iIntervalLength = 0; iIntervalLength < intervalSequence.length; iIntervalLength++)// 最外层循环，由增量序列元素个数决定

{

gap = intervalSequence[iIntervalLength]; // 从增量数组序列取出相应的增长序列

int innerArraySize;// 每次内部插入排序的元素个数

if (0 == itemsNum % gap) {

innerArraySize = itemsNum / gap;

} else {

innerArraySize = itemsNum / gap + 1;

}

for (int i = 0; i < gap; i++) {

int temp = 0;

int out = 0, in = 0;

if (i + (innerArraySize - 1) * gap >= itemsNum) {

innerArraySize--;

}

// 内部用插入排序

for (int j = 1; j < innerArraySize; j++) {

out = i + j * gap;

temp = sources[out];

in = out;

while (in > gap - 1 && sources[in - gap] > temp) {

sources[in] = sources[in - gap];

in = in - gap;

}

sources[in] = temp;

}

}

System.out.print("增长序列为: " + gap + " ");

this.displayArray()ylivUFurlT;

}

}

/**

* 初始化待排序数组

*/

public void initArray(int[] array) {

for (int i = 0; i < array.length; i++) {

sources[i] = array[i];

}

itemsNum = array.length;

}

/**

* 显示数组内容

*/

public void displayArray() {

for (int i = 0; i < itemsNum; i++) {

System.out.print("\t" + sources[i] + " ");

}

System.out.println("\n");

}

public static void main(String[] args) {

int[] intervalSequence = { 5, 3, 1 };

int[] source = { 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };

ShellSortTest2 ss = new ShellSortTest2(source, intervalSequence);

// 初始化待排序数组

ss.initArray(source);

System.out.print("原始序列： ");

ss.displayArray();

// 希尔排序

ss.shellSort();

System.out.print("最后结果： ");

ss.displayArray();

}

}

运行结果如下：

原始序列： 49 38 65 97 76 13 27 49 55 4

增长序列为: 5 13 27 49 55 4 49 38 65 97 76

增长序列为: 3 13 4 49 38 27 49 55 65 97 76

增长序列为: 1 4 13 27 38 49 49 55 65 76 97

最后结果： 4 13 27 38 49 49 55 65 76 97

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。