希爾排序
希爾排序(縮小增量法) 屬于插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序舟山。希爾排序并不穩(wěn)定，O(1)的額外空間累盗，時間復雜度為O(N*(logN)^2)。最壞的情況下的執(zhí)行效率和在平均情況下的執(zhí)行效率相比相差不多符相。
希爾排序間隔序列函數(shù) h = h * 3+ 1
希爾排序比插入排序快很多的原因：當h值很大時蠢琳，數(shù)據(jù)項每一趟排序移動的元素個數(shù)少，但移動的距離很長傲须，這是非常高效的；當h值減小時例衍，每一趟排序移動的元素個數(shù)增加已卸，但此時的數(shù)據(jù)項已經(jīng)接近于他們最終排序后的位置，插入排序可以更有效
public class ShellSort {
static void sort(int[] array) {
int out, in, tmp;
int len = array.length;
int h = 1;
while(h < len / 3) // 計算間隔h最大值
h = h * 3 + 1;
while(h > 0){ // 能否繼續(xù)通過縮小間隔h來分割數(shù)據(jù)列的判定
/*
* out為什么從h開始梦抢？你分割后的第一子序列應該是這樣一個序列永乌，0, h, 2h, 3h, ...
* 插入排序的while循環(huán)是從1開始的，因為第一個數(shù)始終有序圈驼，不需要比較望几，這個需要了解插入排序的算法，所以比較是從第二個數(shù)據(jù)線橄抹，就是數(shù)組的第h個下標開始
* out的判定為什么是out < len？
* 控制數(shù)組下標玉锌，下面的例子會說道
*
* 下面舉一個例子來解釋
* 假定有一個10個數(shù)據(jù)項的數(shù)組疟羹，數(shù)組下標從0 ~ 9 表示
* 當h = 4時的子序列情況是這樣的禀倔，以下標表示
* （0 4 8）（1 5 9）（2 6）（3 7）
* 我第一次是這么理解的参淫，真對每一組分別進行插入排序（當然也可以這樣實現(xiàn)，但是下標不好控制）鞋既，但是對下面的代碼來說這是錯誤的理解耍铜。
* 正確的過程是這樣的，外層for循環(huán)每次對每一分組的前兩個數(shù)據(jù)項進行插入排序业扒，然后前3個，然后前4個 ... 這個和子序列個數(shù)有關
* 排序過程只真對方括號進行
* 當out = 4時進行如下過程 （[0 4] 8）
* 當out = 5時（[1 5] 9）
* 當out = 6時（[2 6]）
* 當out = 7時（[3 7]）
* 當out = 8時（[0 4 8]）
* 當out = 9時（[1 5 9]）
* h = 4執(zhí)行完畢，然后h = (h - 1) / 3 = 1開始新的for循環(huán)
* h = 1時執(zhí)行過程和h = 4時一樣章鲤，不過這時的子數(shù)列就是原始的數(shù)列咆贬，蛻變?yōu)橐粋€簡單的插入排序，這是數(shù)組基本有序掏缎，數(shù)據(jù)項移動次數(shù)會大大減少
*
*/
for(out = h; out < len; out++){ // 外層通過out確定每組插入排序的第二個數(shù)據(jù)項
// 以下代碼就是對子序列進行的插入排序算法
tmp = array[out];
in = out;
/*
* 比較插入排序while循環(huán)的寫法，這里的while循環(huán)與h有關沪哺，所以判定就與h有關酌儒，包括 in -= h語句
* while(in > 0 && array[in - 1] > tmp){
* array[in] = array[in - 1];
* in--;
* }
* array[in] = tmp;
*
*/
while(in > h -1 && array[in - h] >= tmp){
array[in] = array[in - h];
in -= h;
}
array[in] = tmp;
}
// 縮小間隔
h = (h - 1) / 3;
}
}
}
快速排序
算法思想：基于分治的思想，是冒泡排序的改進型籍滴。首先在數(shù)組中選擇一個基準點（該基準點的選取可能影響快速排序的效率榴啸，后面講解選取的方法），然后分別從數(shù)組的兩端掃描數(shù)組勋功，設兩個指示標志（lo指向起始位置坦报，hi指向末尾)燎竖，首先從后半部分開始要销，如果發(fā)現(xiàn)有元素比該基準點的值小，就交換lo和hi位置的值疏咐，然后從前半部分開始掃秒，發(fā)現(xiàn)有元素大于基準點的值借跪，就交換lo和hi位置的值酌壕，如此往復循環(huán)，直到lo>=hi,然后把基準點的值放到hi這個位置卵牍。一次排序就完成了。以后采用遞歸的方式分別對前半部分和后半部分排序辛掠，當前半部分和后半部分均有序時該數(shù)組就自然有序了释牺。
快速排序的時間復雜度為O(NlogN).
public static int partition(int []array,int lo,int hi){
//固定的切分方式
int key=array[lo];//分組最右端為基準值
while(lo<hi){
while(array[hi]>=key&&hi>lo){//從后半部分向前掃描
hi--;
}
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo){從前半部分向后掃描
lo++;
}
array[hi]=array[lo];
}
array[hi]=key;
return hi;
}
public static void sort(int[] array,int lo ,int hi){
if(lo>=hi){
return ;
}
int index=partition(array,lo,hi);
sort(array,lo,index-1);
sort(array,index+1,hi);
}
快速排序的優(yōu)化
對于基準位置的選取一般有三種方法：固定切分没咙，隨機切分和三取樣切分。固定切分的效率并不是太好镜撩，隨機切分是常用的一種切分，效率比較高宜鸯，最壞情況下時間復雜度有可能為O(N2).對于三數(shù)取中選擇基準點是最理想的一種遮怜。
下列代碼替換每個分組基準值
//三數(shù)取中
int mid=lo+(hi-lo)/2;
if(array[mid]>array[hi]){
swap(array[mid],array[hi]);
}
if(array[lo]>array[hi]){
swap(array[lo],array[hi]);
}
if(array[mid]>array[lo]){
swap(array[mid],array[lo]);
}
int key=array[lo];
鏈接
希爾：http://blog.csdn.net/zhqingyun163/article/details/8961396
快排：http://www.cnblogs.com/coderising/p/5708801.html
