希尔排序

希尔排序是插入排序的优化版。

回忆一下插入排序，假如插入排序执行到一半的时候，这时数组左边是已经排好序的，而右边是还没有排序的。如果有一个很小的数据项恰好在右边的位置，这时所有左边已排好序的数组都得往右移，腾出空位让这个小的数据项插入。

希尔排序是在插入算法的基础上再次降低交换的次数，以此获取性能的提升。

public static void sort(int[] list) { int swap_count = 0; int length = list.length; int h = 1; while(h <= length / 3){ h = h * 3 + 1; } while(h > 0){ for(int i = h; i < length; i++){ int temp = list[i]; int insert = i; while(insert > h - 1 && list[insert - h] >= temp){ list[insert] = list[insert - h]; insert -= h; swap_count++; } if(i != insert){ list[insert] = temp; swap_count++; } } // 完成一轮排序 h = (h - 1) / 3; // 缩小间隔 } System.out.println("共交换:" + swap_count); }

我们用图片来稍微说明一下：

假如我们待排序的数组从左至右排列如下，很明显这是一个降序排列，现在我们要将它变成升序排序

看看插入排序怎么做？

这是插入排序执行到将近一半时，数组的排序情况，左边比较齐整的一部分是已排序完成的

每插入一个数据项至左边，都将迫使已排序好的数组整体向右移动，已排好序的数组越大，移动的代价也将越大

看看希尔排序怎么做？

以40为间隔排序后，数组被隔成一堆一堆的局部有序的排列

以13为间隔排序后，数组再次被隔成更小的一堆一堆局部有序的排列

不断缩小间隔h，直至h=0，排序完毕

数组被隔成一段一段的局部有序排列，并且每一段排列也是有序的。

数组的整体移动就限于这个局部之中了，不会发生像插入排序那样将整个已排序数组全部右移的情况，这样就较插入排序更进一步减少了交换的次数。

(图片取自robert lafore《Java数据结构与算法》随书附带源码生成)