细致解读希尔排序算法与相关的Java代码实现

细致解读希尔排序算法与相关的Java代码实现

希尔排序（Shell's sort）是一种非常“神奇”的排序算法。说它“神奇”，是因为没有任何人能清楚地说明它的性能到底能到什么情况。希尔排序因DL．Shell于1959年提出而得名。自从C. A. R. Hoare在1962年提出快速排序后，由于其更为简单，一般采用快速排序。但是，不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度。作为普通程序员，我们可以学习下希尔的思路。

顺便说一句，在希尔排序出现之前，计算机界普遍存在“排序算法不可能突破O(n2)”的观点。希尔排序的出现打破了这个魔咒，很快，快速排序等算法相继问世。从这个意义上说，希尔排序带领我们走向了一个新的时代。

算法概述/思路

希尔排序的提出，主要基于以下两点：

1.插入排序算法在数组基本有序的情况下，可以近似达到O(n)复杂度，效率极高。

2.但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化。

基于此，我们可以使用一种分组的插入排序方法，具体做法是：（以一个16元素大小的数组为例）

1.选择一个增量delta，该增量大于1，从数组中按此增量选择出子数组进行一次直接插入排序。例如，若选择增量为5，则对下标为0，5，10，15的元素进行排序。

2.保留该增量delta并依次移动首个元素进行直接插入排序，直到一轮完成。对于上面的例子，则依次对数组[1，6，11]，[2，7，12]，[3，8，13]，[4，9，14]进行排序。

3.减小增量，不断重复上述过程，直到增量减小为1.显然，最后一次为直接插入排序。

4.排序完成。

从上面可以看出，增量是不断减小的，因此，希尔排序又被成为“缩小增量排序”。

代码实现

package sort;

public class ShellSortTest {

public static int count = 0;

public static void main(String[] args) {

int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };

print(data);

shellSort(data);

print(data);

}

public static void shellSort(int[] data) {

wJMGBse // 计算出最大的h值

int h = 1;

while (h <= data.length / 3) {

h = h * 3 + 1;

}

while (h > 0) {

for (int i = h; i < data.length; i += h) {

if (data[i] < data[i - h]) {

int tmp = data[i];

int j = i - h;

while (j >= 0 && data[j] > tmp) {

data[j + h] = data[j];

j -= h;

http:// }

data[j + h] = tmp;

print(data);

}

}

// 计算出下一个h值

h = (h - 1) / 3;

}

}

public static void print(int[] data) {

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

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

}

System.out.println();

}

}

运行结果：

5 3 6 2 1 9 4 8 7

1 3 6 2 5 9 4 8 7

1 2 3 6 5 9 4 8 7

1 2 3 5 6 9 4 8 7

1 2 3 4 5 6 9 8 7

1 2 3 4 5 6 8 9 7

1 2 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

算法性能/复杂度

希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为1（因为要保证按1有序）。但是，不同的数列选取会对算法的性能造成极大的影响。上面的代码演示了两种增量。

切记：增量序列中每两个元素最好不要出现1以外的公因子！（很显然，按4有序的数列再去按2排序意义并不大）。

下面是一些常见的增量序列。

第一种增量是最初Donald Shell提出的增量，即折半降低直到1。据研究，使用希尔增量，其时间复杂度还是O(n2)。

第二种增量Hibbard：{1, 3, ..., 2^k-1}。该增量序列的时间复杂度大约是O(n^1.5)。

第三种增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1。

算法稳定性

我们都知道插入排序是稳定算法。但是，Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏，因此，Shell排序不是一个稳定的算法。

算法适用场景

Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀--快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。

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