算法簡介
希爾排序的由來：1959 年 Shell 發(fā)明银室；第一個(gè)突破 O(n^2) 的排序算法磺浙；是簡單插入排序的改進(jìn)版护盈；它與插入排序的不同之處在于堂湖，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素闲先。希爾排序又叫縮小增量排序。
基本思路
希爾排序?yàn)榱思涌焖俣群唵蔚母倪M(jìn)了插入排序无蜂，交換不相鄰的元素以對(duì)數(shù)組的局部進(jìn)行排序伺糠，并最終用插入排序將局部有序的數(shù)組排序。（局部有序的數(shù)組很適合插入排序）
Q：希爾排序的思想斥季？
A：使數(shù)組中任意間隔為 h 的元素都是有序的训桶。這樣的數(shù)組被稱為 h 有序數(shù)組，也就是說：一個(gè) h 有序數(shù)組就是 h 個(gè)相互獨(dú)立的有序數(shù)組編織在一起組成的一個(gè)數(shù)組泻肯。
Q：它的一種實(shí)現(xiàn)方法渊迁？
A：在插入排序的代碼中將移動(dòng)元素的距離由 1 改為 h 即可。
Q：h 的取值灶挟？
A：增幅 h 的初始值是數(shù)組長度乘以一個(gè)常數(shù)因子，最小為 1 毒租。 例如： while( h < arr.length/3 ) h = 3 * h + 1 稚铣； //（1箱叁、4、13惕医、40耕漱、121、364抬伺、1093…）
嘗試使用 while( h < arr.length/5 ) h = 5 * h + 1 螟够；// 1、6峡钓、31妓笙、156、781... 能岩，速度會(huì)變快寞宫。
優(yōu)點(diǎn)：希爾排序?qū)τ谥械却笮〉臄?shù)組，運(yùn)行時(shí)間是可以接受的拉鹃，代碼量少辈赋，且不需要使用額外的內(nèi)存空間。
運(yùn)行軌跡
增幅 h 的初始值是數(shù)組長度乘以一個(gè)常數(shù)因子膏燕，最小為 1 钥屈。
當(dāng) h = 4 時(shí)，4-sort坝辫；
當(dāng) h = 1 時(shí)焕蹄，1-sort；
代碼實(shí)現(xiàn)
根據(jù)排序算法類的模板實(shí)現(xiàn)希爾排序（提醒：點(diǎn)藍(lán)字查看詳情）
import java.util.Random;
/**
* 希爾排序
*
* @author TinyDolphin
* 2017/5/30 22:33.
*/
public class Shell {
/**
* 排序?qū)崿F(xiàn)
*
* @param arr 待排序數(shù)組
*/
public static void sort(Comparable[] arr) {
int length = arr.length;
int h = 1;
while (h < length / 3) {
h = 3 * h + 1; // 1 , 4 , 13 , 40 , 121 , 364 , 1093...
}
while (h >= 1) {
// 將數(shù)組變?yōu)?h 有序
for (int indexI = h; indexI < length; indexI++) {
for (int indexJ = indexI; indexJ >= h && less(arr[indexJ], arr[indexJ - h]); indexJ -= h) {
exch(arr, indexJ, indexJ - h);
}
}
h = h / 3;
}
}
/**
* 比較兩個(gè)元素的大小
*
* @param comparableA 待比較元素A
* @param comparableB 待比較元素B
* @return 若 A < B,返回 true,否則返回 false
*/
private static boolean less(Comparable comparableA, Comparable comparableB) {
return comparableA.compareTo(comparableB) < 0;
}
/**
* 將兩個(gè)元素交換位置
*
* @param arr 待交換元素所在的數(shù)組
* @param indexI 第一個(gè)元素索引
* @param indexJ 第二個(gè)元素索引
*/
private static void exch(Comparable[] arr, int indexI, int indexJ) {
Comparable temp = arr[indexI];
arr[indexI] = arr[indexJ];
arr[indexJ] = temp;
}
/**
* 打印數(shù)組的內(nèi)容
*
* @param arr 待打印的數(shù)組
*/
private static void show(Comparable[] arr) {
for (int index = 0; index < arr.length; index++) {
System.out.print(arr[index] + " ");
}
System.out.println();
}
/**
* 判斷數(shù)組是否有序
*
* @param arr 待判斷數(shù)組
* @return 若數(shù)組有序，返回 true更振，否則返回 false
*/
public static boolean isSort(Comparable[] arr) {
for (int index = 1; index < arr.length; index++) {
if (less(arr[index], arr[index - 1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Integer[] arr = new Integer[100000];
for (int index = 0; index < 100000; index++) {
arr[index] = new Random().nextInt(100000) + 1;
}
long start = System.currentTimeMillis();
sort(arr); //耗費(fèi)時(shí)間：480ms
long end = System.currentTimeMillis();
System.out.println("耗費(fèi)時(shí)間：" + (end - start) + "ms");
assert isSort(arr);
}
}
性能分析
最佳情況：T(n) = O(nlog2n)
最壞情況：T(n) = O(nlog2n)
平均情況：T(n) = O(nlogn)
算法的性能不僅取決于 h 炕桨， 還取決于 h 之間的數(shù)學(xué)性質(zhì)，比如它們的公因子等肯腕。
使用遞增序列 1献宫、4、13实撒、40姊途、121涉瘾、364… 的希爾排序所需的比較次數(shù)不會(huì)超過 N 的若干倍乘以遞增序列的長度。
Q：如何通過h遞增序列優(yōu)化捷兰？
A：在實(shí)際應(yīng)用中立叛，h 的取值使用以上遞增序列基本就足夠了。但是我們?yōu)榱俗非笮阅艿奶嵘泵彩褂靡韵碌男蛄忻厣撸剐阅芴岣?20%-40% 。1顶考、5赁还、19、41村怪、109秽浇、209、505甚负、929柬焕、2161、3905梭域、8929斑举、16001、36289病涨、64769富玷、146305、260609（這是通過 9×4k-9×2k+1(k=1,2,3,4,5…) 和 4k-3×2k+1(k=2,3,4,5,6…) 綜合得到的）
Q：希爾排序?yàn)槭裁锤痈咝В?/strong>
A：它權(quán)衡了子數(shù)組的規(guī)模和有序性既穆。
Q：和選擇排序以及插入排序形成對(duì)比的是：
A：希爾排序也可以用于大型數(shù)組赎懦。它對(duì)任意排序（不一定是隨機(jī)的）的數(shù)組表現(xiàn)也很好。希爾排序比插入排序和選擇排序要快的多幻工，并且數(shù)組越大励两，優(yōu)勢越大∧衣【提示：點(diǎn)擊藍(lán)色字體当悔，可以查看其詳細(xì)信息√叽】
Q：什么時(shí)候用希爾排序盲憎？
A： 當(dāng)你需要解決一個(gè)排序問題而又沒有系統(tǒng)排序函數(shù)可用（例如直接接觸硬件或是運(yùn)行于嵌入式系統(tǒng)中的代碼）時(shí)，可用先用希爾排序胳挎，然后再考慮是否值得將它替換為更加復(fù)雜的排序算法饼疙。
※ 研究算法的設(shè)計(jì)和性能的主要原因之一：通過提升速度來解決其他方式無法解決的問題。
優(yōu)化方案
NO.1
使用更為復(fù)雜的遞增序列串远，性能可以提高 20%-40% 宏多。（這里就不說了儿惫，上述的遞增序列夠用）
NO.2
因?yàn)槭腔诓迦肱判虻脑璺＃钥梢允褂闷?a href="http://www.reibang.com/p/df8fac515214" target="_blank">插入排序及其優(yōu)化中給出的優(yōu)化方案伸但。即：進(jìn)行了預(yù)處理操作，并在內(nèi)循環(huán)中留搔，總是將較大的元素向右移動(dòng)更胖。原方案是交換。
優(yōu)化之后運(yùn)行軌跡
優(yōu)化之后代碼
public static void sortPlus(Comparable[] arr) {
int length = arr.length;
int h = 1;
while (h < length / 3) {
h = 3 * h + 1; // 1 , 4 , 13 , 40 , 121 , 364 , 1093...
}
int exchanges = 0; //交換次數(shù)
//若 arr[index] < arr[index - 1]隔显，則交換兩數(shù)
for (int index = length - 1; index > 0; index--) {
if (less(arr[index], arr[index - 1])) {
exch(arr, index, index - 1);
exchanges++;
}
}
//若交換次數(shù)為0（即數(shù)組有序）却妨，則無需進(jìn)行下一步排序。
if (exchanges == 0) return;
//若有交換次數(shù)括眠，表明目前的數(shù)組無序彪标。
while (h >= 1) {
// 將數(shù)組變?yōu)?h 有序
for (int indexI = h; indexI < length; indexI++) {
Comparable temp = arr[indexI]; //記錄一下arr[indexI]的值
int indexJ = indexI; //indexI 的代替品
//若 indexJ 的前 h 位元素小于 temp，則將小于temp的元素向右移動(dòng) h 位
//需要注意：可能會(huì)出現(xiàn) indexJ < h 的情況掷豺。而一般的插入排序不會(huì)出現(xiàn)捞烟。
while (indexJ >= h && less(temp, arr[indexJ - h])) {
arr[indexJ] = arr[indexJ - h];
indexJ -= h;
}
arr[indexJ] = temp; //將記錄的值放在 indexJ 的位置上
}
h = h / 3;
}
}
測試代碼
【高效復(fù)制數(shù)組的方法】，提示：點(diǎn)擊藍(lán)色字體查看方法詳情当船。
public static void main(String[] args) {
int length = 1000000; // 百萬數(shù)據(jù)量級(jí)別
Integer[] arr = new Integer[length];
Integer[] arr2 = new Integer[length];
for (int index = 0; index < length; index++) {
arr[index] = new Random().nextInt(length) + 1;
}
//高效復(fù)制數(shù)組的方法
System.arraycopy(arr, 0, arr2, 0, arr.length);
long start = System.currentTimeMillis();
sort(arr);
long end = System.currentTimeMillis();
System.out.println("耗費(fèi)時(shí)間：" + (end - start) + "ms");
assert isSort(arr);
start = System.currentTimeMillis();
sortPlus(arr2);
end = System.currentTimeMillis();
System.out.println("耗費(fèi)時(shí)間：" + (end - start) + "ms");
assert isSort(arr2);
}
測試結(jié)果
注意：編譯器默認(rèn)不適用 assert 檢測（但是junit測試中適用）题画，所以要使用時(shí)要添加參數(shù)虛擬機(jī)啟動(dòng)參數(shù)-ea
具體添加過程，請(qǐng)參照eclipse 和 IDEA 設(shè)置虛擬機(jī)啟動(dòng)參數(shù)
