在Java數(shù)據(jù)結(jié)構(gòu)和算法（三）——冒泡、選擇、插入排序算法中我們介紹了三種簡單的排序算法，它們的時間復(fù)雜度大O表示法都是O(N2)，如果數(shù)據(jù)量少，我們還能忍受，但是數(shù)據(jù)量大，那么這三種簡單的排序所需要的時間則是我們所不能接受的。接著我們在講解遞歸 的時候，介紹了歸并排序，歸并排序需要O(NlogN)，這比簡單排序要快了很多，但是歸并排序有個缺點，它需要的空間是原始數(shù)組空間的兩倍，當(dāng)我們需要排序的數(shù)據(jù)占據(jù)了整個內(nèi)存的一半以上的空間，那么是不能使用歸并排序的。
本篇博客將介紹幾種高級的排序算法：希爾排序和快速排序。
1、希爾排序
希爾排序是基于直接插入排序的，它在直接插入排序中增加了一個新特性，大大的提高了插入排序的執(zhí)行效率。所以在講解希爾排序之前，我們先回顧一下直接插入排序。
①、直接插入排序
直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。
實現(xiàn)代碼為：
public class InsertSort {
public static int[] sort(int[] array){
int j;
//從下標(biāo)為1的元素開始選擇合適的位置插入，因為下標(biāo)為0的只有一個元素，默認(rèn)是有序的
for(int i = 1 ; i < array.length ; i++){
int tmp = array[i];//記錄要插入的數(shù)據(jù)
j = i;
while(j > 0 && tmp < array[j-1]){//從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
array[j] = array[j-1];//向后挪動
j--;
}
array[j] = tmp;//存在比其小的數(shù)，插入
}
return array;
}
}
我們可以分析一下這個直接插入排序，首先我們將需要插入的數(shù)放在一個臨時變量中，這也是一個標(biāo)記符，標(biāo)記符左邊的數(shù)是已經(jīng)排好序的，標(biāo)記符右邊的數(shù)是需要排序的。接著將標(biāo)記的數(shù)和左邊排好序的數(shù)進(jìn)行比較，假如比目標(biāo)數(shù)大則將左邊排好序的數(shù)向右邊移動一位，直到找到比其小的位置進(jìn)行插入。
這里就存在一個效率問題了，如果一個很小的數(shù)在很靠近右邊的位置，比如上圖右邊待排序的數(shù)據(jù) 1 ，那么想讓這個很小的數(shù) 1 插入到左邊排好序的位置，那么左邊排好序的數(shù)據(jù)項都必須向右移動一位，這個步驟就是將近執(zhí)行了N次復(fù)制，雖然不是每個數(shù)據(jù)項都必須移動N個位置，但是每個數(shù)據(jù)項平均移動了N/2次，總共就是N2/2，因此插入排序的效率是O(N2)。
那么如果以某種方式不必一個一個移動中間所有的數(shù)據(jù)項，就能把較小的數(shù)據(jù)項移動到左邊，那么這個算法的執(zhí)行效率會有很大的改進(jìn)。
?、?、希爾排序圖解
希爾排序應(yīng)運而生了，希爾排序通過加大插入排序中元素的間隔，并在這些有間隔的元素中進(jìn)行插入排序，從而使數(shù)據(jù)項能夠大跨度的移動。當(dāng)這些數(shù)據(jù)項排過一趟序后，希爾排序算法減小數(shù)據(jù)項的間隔再進(jìn)行排序，依次進(jìn)行下去，最后間隔為1時，就是我們上面說的簡單的直接插入排序。
下圖顯示了增量為4時對包含10個數(shù)組元素進(jìn)行排序的第一個步驟，首先對下標(biāo)為 0,4,8 的元素進(jìn)行排序，完成排序之后，算法右移一步，對 1,5,9 號元素進(jìn)行排序，依次類推，直到所有的元素完成一趟排序，也就是說間隔為4的元素都已經(jīng)排列有序。
當(dāng)我們完成4-增量排序之后，在進(jìn)行普通的插入排序，即1-增量排序，會比前面直接執(zhí)行簡單插入排序要快很多。
?、?、排序間隔選取
對于10個元素，我們選取4的間隔，那么100個數(shù)據(jù)，1000個數(shù)據(jù)，甚至更多的數(shù)據(jù)，我們應(yīng)該怎么選取間隔呢？
希爾的原稿中，他建議間隔選為N/2，也就是每一趟都將排序分為兩半，因此對于N=100的數(shù)組，逐漸減小的間隔序列為：50,25,12，6,3,1。這個方法的好處是不需要在開始排序前為找到初始序列的間隔而計算序列，只需要用2整除N。但是這已經(jīng)被證明并不是最好的序列。
間隔序列中的數(shù)字互質(zhì)是很重要的指標(biāo)，也就是說，除了1，他們沒有公約數(shù)。這個約束條件使得每一趟排序更有可能保持前一趟排序已經(jīng)排好的結(jié)果，而希爾最初以N/2的間隔的低效性就是沒有遵守這個準(zhǔn)則。
所以一種希爾的變形方法是用2.2來整除每一個間隔，對于n=100的數(shù)組，會產(chǎn)生序列45，20，9,4,1。這比用2會整除會顯著的改善排序效果。
還有一種很常用的間隔序列：knuth 間隔序列 3h+1
但是無論是什么間隔序列，最后必須滿足一個條件，就是逐漸減小的間隔最后一定要等于1，因此最后一趟排序一定是簡單的插入排序。
下面我們通過knuth間隔序列來實現(xiàn)希爾排序：
?、?、knuth間隔序列的希爾排序算法實現(xiàn)
//希爾排序 knuth 間隔序列 3h+1
public static void shellKnuthSort(int[] array){
System.out.println("原數(shù)組為"+Arrays.toString(array));
int step = 1 ;
int len = array.length;
while(step <= len/3){
step = step*3 + 1;//1,4,13,40......
}
while(step > 0){
//分別對每個增量間隔進(jìn)行排序
for(int i = step ; i < len ; i++){
int temp = array[i];
int j = i;
while(j > step-1 && temp <= array[j-step]){
array[j] = array[j-step];
j -= step;
}
array[j] = temp;
}//end for
System.out.println("間隔為"+step+"的排序結(jié)果為"+Arrays.toString(array));
step = (step-1)/3;
}//end while(step>0)
System.out.println("最終排序："+Arrays.toString(array));
}
測試結(jié)果：
public static void main(String[] args) {
int[] array = {4,2,8,9,5,7,6,1,3,10};
shellKnuthSort(array);
}
⑤、間隔為2h的希爾排序
//希爾排序 間隔序列2h
public static void shellSort(int[] array){
System.out.println("原數(shù)組為"+Arrays.toString(array));
int step;
int len = array.length;
for(step = len/2 ;step > 0 ; step /= 2){
//分別對每個增量間隔進(jìn)行排序
for(int i = step ; i < array.length ; i++){
int j = i;
int temp = array[j];
if(array[j] < array[j-step]){
while(j-step >=0 && temp < array[j-step]){
array[j] = array[j-step];
j -= step;
}
array[j] = temp;
}
}
System.out.println("間隔為"+step+"的排序結(jié)果為"+Arrays.toString(array));
}
}
測試結(jié)果：
2、快速排序
快速排序是對冒泡排序的一種改進(jìn)，由C. A. R. Hoare在1962年提出的一種劃分交換排序，采用的是分治策略（一般與遞歸結(jié)合使用），以減少排序過程中的比較次數(shù)。
①、快速排序的基本思路
一、先通過第一趟排序，將數(shù)組原地劃分為兩部分，其中一部分的所有數(shù)據(jù)都小于另一部分的所有數(shù)據(jù)。原數(shù)組被劃分為2份
二、通過遞歸的處理， 再對原數(shù)組分割的兩部分分別劃分為兩部分，同樣是使得其中一部分的所有數(shù)據(jù)都小于另一部分的所有數(shù)據(jù)。 這個時候原數(shù)組被劃分為了4份
三、就1,2被劃分后的最小單元子數(shù)組來看，它們?nèi)匀皇菬o序的，但是！ 它們所組成的原數(shù)組卻逐漸向有序的方向前進(jìn)。
四、這樣不斷劃分到最后，數(shù)組就被劃分為多個由一個元素或多個相同元素組成的單元，這樣數(shù)組就有序了。
具體實例：
對于上圖的數(shù)組[3,1,4,1,5,9,2,6,5,3]，通過第一趟排序?qū)?shù)組分成了[2,1,1]或[4,5,9,3,6,5,3]兩個子數(shù)組，且對于任意元素，左邊子數(shù)組總是小于右邊子數(shù)組。通過不斷的遞歸處理，最終得到有序數(shù)組[1 1 2 3 3 4 5 5 6]
②、快速排序的算法實現(xiàn)
假設(shè)被排序的無序區(qū)間為[A[i],......,A[j]]
一、基準(zhǔn)元素選?。?/strong>選擇其中的一個記錄的關(guān)鍵字 v 作為基準(zhǔn)元素（控制關(guān)鍵字）;怎么選取關(guān)鍵字？
二、劃分：通過基準(zhǔn)元素 v 把無序區(qū)間 A[I]......A[j] 劃分為左右兩部分，使得左邊的各記錄的關(guān)鍵字都小于 v；右邊的各記錄的關(guān)鍵字都大于等于 v；（如何劃分？）
三、遞歸求解：重復(fù)上面的一、二步驟，分別對左邊和右邊兩部分遞歸進(jìn)行快速排序。
四、組合：左、右兩部分均有序，那么整個序列都有序。
上面的第 三、四步不用多說，主要是第一步怎么選取關(guān)鍵字，從而實現(xiàn)第二步的劃分？
劃分的過程涉及到三個關(guān)鍵字：“基準(zhǔn)元素”、“左游標(biāo)”、“右游標(biāo)”
基準(zhǔn)元素：它是將數(shù)組劃分為兩個子數(shù)組的過程中，用于界定大小的值，以它為判斷標(biāo)準(zhǔn)，將小于它的數(shù)組元素“劃分”到一個“小數(shù)值的數(shù)組”中，而將大于它的數(shù)組元素“劃分”到一個“大數(shù)值的數(shù)組”中，這樣，我們就將數(shù)組分割為兩個子數(shù)組，而其中一個子數(shù)組的元素恒小于另一個子數(shù)組里的元素。
左游標(biāo)：它一開始指向待分割數(shù)組最左側(cè)的數(shù)組元素，在排序的過程中，它將向右移動。
右游標(biāo)：它一開始指向待分割數(shù)組最右側(cè)的數(shù)組元素，在排序的過程中，它將向左移動。
注意：上面描述的基準(zhǔn)元素/右游標(biāo)/左游標(biāo)都是針對單趟排序過程的， 也就是說，在整體排序過程的多趟排序中，各趟排序取得的基準(zhǔn)元素/右游標(biāo)/左游標(biāo)一般都是不同的。
對于基準(zhǔn)元素的選取，原則上是任意的。但是一般我們選取數(shù)組中第一個元素為基準(zhǔn)元素（假設(shè)數(shù)組是隨機分布的）
③、快速排序圖示
[圖片上傳中...(image-f70433-1527743588444-4)]
上面表示的是一個無序數(shù)組，選取第一個元素 6 作為基準(zhǔn)元素。左游標(biāo)是 i 哨兵，右游標(biāo)是 j 哨兵。然后左游標(biāo)向左移動，右游標(biāo)向右移動，它們遵循的規(guī)則如下：
一、左游標(biāo)向右掃描， 跨過所有小于基準(zhǔn)元素的數(shù)組元素, 直到遇到一個大于或等于基準(zhǔn)元素的數(shù)組元素， 在那個位置停下。
二、右游標(biāo)向左掃描， 跨過所有大于基準(zhǔn)元素的數(shù)組元素, 直到遇到一個小于或等于基準(zhǔn)元素的數(shù)組元素，在那個位置停下。
第一步：哨兵 j 先開始出動。因為此處設(shè)置的基準(zhǔn)數(shù)是最左邊的數(shù)，所以需要讓哨兵 j 先開始出動，哨兵 j 一步一步的向左挪動，直到找到一個小于 6 的元素停下來。接下來，哨兵 i 再一步一步的向右挪動，直到找到一個大于 6 的元素停下來。最后哨兵 i 停在了數(shù)字 7 面前，哨兵 j 停在了數(shù)字 5 面前。
到此，第一次交換結(jié)束，接著哨兵 j 繼續(xù)向左移動，它發(fā)現(xiàn) 4 比基準(zhǔn)數(shù) 6 要小，那么在數(shù)字4面前停下來。哨兵 i 也接著向右移動，然后在數(shù)字 9 面前停下來，然后哨兵 i 和 哨兵 j 再次進(jìn)行交換。
第二次交換結(jié)束，哨兵 j 繼續(xù)向左移動，然后在數(shù)字 3 面前停下來；哨兵 i 繼續(xù)向右移動，但是它發(fā)現(xiàn)和哨兵 j 相遇了。那么此時說明探測結(jié)束，將數(shù)字 3 和基準(zhǔn)數(shù)字 6 進(jìn)行交換，如下：
到此，第一次探測真正結(jié)束，此時已基準(zhǔn)點 6 為分界線，6 左邊的數(shù)組元素都小于等于6,6右邊的數(shù)組元素都大于等于6。
左邊序列為【3,1,2,5,4】,右邊序列為【9,7,10,8】。接著對于左邊序列而言，以數(shù)字 3 為基準(zhǔn)元素，重復(fù)上面的探測操作，探測完畢之后的序列為【2,1,3,5,4】；對于右邊序列而言，以數(shù)字 9 位基準(zhǔn)元素，也重復(fù)上面的探測操作。然后一步一步的劃分，最后排序完全結(jié)束。
通過這一步一步的分解，我們發(fā)現(xiàn)快速排序的每一輪操作就是將基準(zhǔn)數(shù)字歸位，知道所有的數(shù)都?xì)w位完成，排序就結(jié)束了。
④、快速排序完整代碼
package com.ys.high.sort;
public class QuickSort {
//數(shù)組array中下標(biāo)為i和j位置的元素進(jìn)行交換
private static void swap(int[] array , int i , int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void recQuickSort(int[] array,int left,int right){
if(right <= left){
return;//終止遞歸
}else{
int partition = partitionIt(array,left,right);
recQuickSort(array,left,partition-1);// 對上一輪排序(切分)時，基準(zhǔn)元素左邊的子數(shù)組進(jìn)行遞歸
recQuickSort(array,partition+1,right);// 對上一輪排序(切分)時，基準(zhǔn)元素右邊的子數(shù)組進(jìn)行遞歸
}
}
private static int partitionIt(int[] array,int left,int right){
//為什么 j加一個1，而i沒有加1,是因為下面的循環(huán)判斷是從--j和++i開始的.
//而基準(zhǔn)元素選的array[left],即第一個元素，所以左游標(biāo)從第二個元素開始比較
int i = left;
int j = right+1;
int pivot = array[left];// pivot 為選取的基準(zhǔn)元素（頭元素）
while(true){
while(i<right && array[++i] < pivot){}
while(j > 0 && array[--j] > pivot){}
if(i >= j){// 左右游標(biāo)相遇時候停止， 所以跳出外部while循環(huán)
break;
}else{
swap(array, i, j);// 左右游標(biāo)未相遇時停止, 交換各自所指元素，循環(huán)繼續(xù)
}
}
swap(array, left, j);//基準(zhǔn)元素和游標(biāo)相遇時所指元素交換，為最后一次交換
return j;// 一趟排序完成， 返回基準(zhǔn)元素位置(注意這里基準(zhǔn)元素已經(jīng)交換位置了)
}
public static void sort(int[] array){
recQuickSort(array, 0, array.length-1);
}
//測試
public static void main(String[] args) {
//int[] array = {7,3,5,2,9,8,6,1,4,7};
int[] array = {9,9,8,7,6,5,4,3,2,1};
sort(array);
for(int i : array){
System.out.print(i+" ");
}
//打印結(jié)果為：1 2 3 4 5 6 7 7 8 9
}
}
⑤、優(yōu)化分析
假設(shè)我們是對一個逆序數(shù)組進(jìn)行排序，選取第一個元素作為基準(zhǔn)點，即最大的元素是基準(zhǔn)點，那么第一次循環(huán)，左游標(biāo)要執(zhí)行到最右邊，而右游標(biāo)執(zhí)行一次，然后兩者進(jìn)行交換。這也會劃分成很多的子數(shù)組。
那么怎么解決呢？理想狀態(tài)下，應(yīng)該選擇被排序數(shù)組的中值數(shù)據(jù)作為基準(zhǔn)，也就是說一半的數(shù)大于基準(zhǔn)數(shù)，一般的數(shù)小于基準(zhǔn)數(shù)，這樣會使得數(shù)組被劃分為兩個大小相等的子數(shù)組，對快速排序來說，擁有兩個大小相等的子數(shù)組是最優(yōu)的情況。
三項取中劃分
為了找到一個數(shù)組中的中值數(shù)據(jù)，一般是取數(shù)組中第一個、中間的、最后一個，選擇這三個數(shù)中位于中間的數(shù)。
//取數(shù)組下標(biāo)第一個數(shù)、中間的數(shù)、最后一個數(shù)的中間值
private static int medianOf3(int[] array,int left,int right){
int center = (right-left)/2+left;
if(array[left] > array[right]){ //得到 array[left] < array[right]
swap(array, left, right);
}
if(array[center] > array[right]){ //得到 array[left] array[center] < array[right]
swap(array, center, right);
}
if(array[center] > array[left]){ //得到 array[center] < array[left] < array[right]
swap(array, center, left);
}
return array[left]; //array[left]的值已經(jīng)被換成三數(shù)中的中位數(shù)， 將其返回
}
private static int partitionIt(int[] array,int left,int right){
//為什么 j加一個1，而i沒有加1,是因為下面的循環(huán)判斷是從--j和++i開始的.
//而基準(zhǔn)元素選的array[left],即第一個元素，所以左游標(biāo)從第二個元素開始比較
int i = left;
int j = right+1;
int pivot = array[left];// pivot 為選取的基準(zhǔn)元素（頭元素）
int size = right - left + 1;
if(size >= 3){
pivot = medianOf3(array, left, right); //數(shù)組范圍大于3，基準(zhǔn)元素選擇中間值。
}
while(true){
while(i<right && array[++i] < pivot){}
while(j > 0 && array[--j] > pivot){}
if(i >= j){// 左右游標(biāo)相遇時候停止， 所以跳出外部while循環(huán)
break;
}else{
swap(array, i, j);// 左右游標(biāo)未相遇時停止, 交換各自所指元素，循環(huán)繼續(xù)
}
}
swap(array, left, j);//基準(zhǔn)元素和游標(biāo)相遇時所指元素交換，為最后一次交換
return j;// 一趟排序完成， 返回基準(zhǔn)元素位置(注意這里基準(zhǔn)元素已經(jīng)交換位置了)
}
處理小劃分
如果使用三數(shù)據(jù)取中劃分方法，則必須遵循快速排序算法不能執(zhí)行三個或者少于三個的數(shù)據(jù)，如果大量的子數(shù)組都小于3個，那么使用快速排序是比較耗時的。聯(lián)想到前面我們講過簡單的排序（冒泡、選擇、插入）。
當(dāng)數(shù)組長度小于M的時候（high-low <= M）， 不進(jìn)行快排，而進(jìn)行插入排序。轉(zhuǎn)換參數(shù)M的最佳值和系統(tǒng)是相關(guān)的，一般來說， 5到15間的任意值在多數(shù)情況下都能令人滿意。
//插入排序
private static void insertSort(int[] array){
for(int i = 1 ; i < array.length ; i++){
int temp = array[i];
int j = i;
while(j > 0 && array[j-1] > temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}
