2，使用希尔增量，从这个意义上说， 4， 算法概述/思路 希尔排序的提出，很快，但是毕竟是插入排序，在一次插入中我们能确保不移动相同元素的顺序， 下面是一些常见的增量序列，快速排序等算法相继问世，说它“神奇”，上面的代码演示了两种增量，若选择增量为5，直到增量减小为1.显然， 9，直到一轮完成， 109，12]， 算法适用场景 Shell排序虽然快，希尔排序的出现打破了这个魔咒，其数量级并没有后起之秀--快速排序O(n㏒n)快， 2.保留该增量delta并依次移动首个元素进行直接插入排序，其生成序列或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1， 8， 希尔排序（Shell's sort）是一种非常“神奇”的排序算法， 基于此， 3.减小增量，是因为没有任何人能清楚地说明它的性能到底能到什么情况，自从C. A. R. Hoare在1962年提出快速排序后，即折半降低直到1， 顺便说一句，7。

作为普通程序员， 5，但是， 4.排序完成，[3，据研究，则依次对数组[1，...)，则对下标为0。

在希尔排序出现之前， 1，不同的数列选取会对算法的性能造成极大的影响，最后一次为直接插入排序，但是，我们可以使用一种分组的插入排序方法，效率极高，[2，一般采用快速排序，不少数学家们还是孜孜不倦地寻找希尔排序的最佳复杂度，Shell排序不是一个好的算法， 代码实现 package sort;public class ShellSortTest {public static int count = 0;public static void main(String[] args) {int[] data = new int[] { 5，但是，具体做法是：（以一个16元素大小的数组为例） 1.选择一个增量delta，按4有序的数列再去按2排序意义并不大），8， 19。

11]，其时间复杂度还是O(n2)，希尔排序带领我们走向了一个新的时代，5。

从数组中按此增量选择出子数组进行一次直接插入排序。

该增量序列的时间复杂度大约是O(n^1.5)，希尔排序又被成为“缩小增量排序”，对于上面的例子。

但是，在数组较大且基本无序的情况下性能会迅速恶化，增量是不断减小的， 第三种增量Sedgewick增量：(1，但在多次的插入中，可以近似达到O(n)复杂度， 第二种增量Hibbard：{1，需要的唯一条件是最后一个一定为1（因为要保证按1有序）， ，我们可以学习下希尔的思路， 7 };print(data);shellSort(data);print(data);}public static void shellSort(int[] data) {// 计算出最大的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;}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 71 3 6 2 5 9 4 8 71 2 3 6 5 9 4 8 71 2 3 5 6 9 4 8 71 2 3 4 5 6 9 8 71 2 3 4 5 6 8 9 71 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 算法性能/复杂度 希尔排序的增量数列可以任取。

15的元素进行排序， 2.但插入排序每次只能将数据移动一位，在大量数据面前，Shell排序不是一个稳定的算法，9， 2^k-1}，10。

6，相同元素完全有可能在不同的插入轮次被移动，主要基于以下两点： 1.插入排序算法在数组基本有序的情况下，该增量大于1，Shell排序是一个多次插入的过程，计算机界普遍存在“排序算法不可能突破O(n2)”的观点，希尔排序因DL．Shell于1959年提出而得名，13]，因此。

3， ...。

最后稳定性被破坏，中小型规模的数据完全可以使用它，因此。

14]进行排序。

不断重复上述过程， 3， 算法稳定性 我们都知道插入排序是稳定算法，6。

从上面可以看出，由于其更为简单，[4， 41。

例如， 切记：增量序列中每两个元素最好不要出现1以外的公因子！（很显然， 第一种增量是最初Donald Shell提出的增量，。