本章介紹兩種高級排序尸折，希爾排序和快速排序妆艘，這兩種排序比之前講到的簡單排序都要快很多效扫；希爾排序大約需要O(N*(logN)2)的時間，快速排序的時間復(fù)雜度為(N*logN)席覆，這兩種算法和我們在講遞歸的時候講到的歸并排序不同史辙，不需要大量的輔助存儲空間，快速排序是所有通用排序算法中最快的排序算法娜睛。
希爾排序：
希爾排序是基于插入排序的髓霞，希爾排序在插入排序的基礎(chǔ)之上通過加大插入排序元素之間的間隔，并在這些間隔元素之間進行插入排序畦戒，使數(shù)據(jù)實現(xiàn)大跨度的移動方库，從而使排序更有效率，我們習(xí)慣將排序時數(shù)據(jù)項之間的間隔稱為增量障斋，用h來表示纵潦，下圖表示了十個數(shù)據(jù)項，以增量為4進行第一趟排序后的結(jié)果
通過上面的一趟排序之后我們可以看到元素離他們的最終有序序列位置都很近了垃环，希爾排序就是通過創(chuàng)建這種交錯有序的數(shù)據(jù)項集合邀层，從而提高排序的效率，當(dāng)上面完成了4增量的排序之后遂庄，就可以進行普通的插入排序寥院，這樣就比普通的插入排序的效率要高很多。
上面對于有十個數(shù)據(jù)項的數(shù)組初始增量我們設(shè)置為4涛目，對于數(shù)據(jù)項更大的數(shù)組我們的初始增量也應(yīng)該設(shè)置得更大秸谢，這里我們使用Knuth提出的間隔序列，序列的通項表達式為h=3*h+1霹肝，假設(shè)我們數(shù)據(jù)項的個數(shù)為100估蹄，那么通過Knuth間隔序列1,4,13,40,121,364,1093這里1093大于了我們的數(shù)據(jù)項1000，所以我們?nèi)〕跏嫉脑隽繛?64然后通過Knuth間隔序列依次減小我們的增量值沫换，最終達到我們想要的一個個排序的效果臭蚁，接下來我們給出希爾排序的java代碼
public class ArrayShell {
public long[] theArray;
private int nElems;
public ArrayShell(int size) {
this.theArray = new long[size];
this.nElems = 0;
}
public void insert(long value) {
theArray[nElems++] = value;
}
public void shellSort() {
//首先找到初始增量
int h = 1;
int outer, inner;
while (h <= nElems/3) {
h = 3 * h + 1;
}
while (h > 0) {
//以下就是普通的插入排序，只是步長換為h即可
for (outer = h; outer < nElems; outer++) {
long temp = theArray[outer];
//增量為h讯赏，所以我們首個比較的元素從h開始垮兑，h和第一個索引為0的元素比較大小、h+1和索引為1比較是否交換漱挎。然后以此類推
inner = outer;
while (inner > h - 1 && temp < theArray[inner - h]) { //需要進行數(shù)據(jù)交換的元素的滿足條件
theArray[inner] = theArray[inner - h];
inner -= h;
}
theArray[inner] = temp;
}
//從最大增量一直遞減到1做插入排序
h = (h - 1) / 3;
}
}
}
希爾排序中間隔序列互質(zhì)很重要系枪，他能是每一趟排序更有可能保持前一趟已排序好的效果。
快速排序
快速排序是基于劃分算法之上的一種排序算法识樱，首先我們介紹一下劃分算法的基本原理
劃分
劃分的基本原理就是把數(shù)據(jù)分為兩組嗤无，使關(guān)鍵值大于特定值的數(shù)據(jù)在一組震束，使關(guān)鍵值小于特定值的數(shù)據(jù)在另一組，比如我們?nèi)粘Ｉ钪袑⒓揖嚯x辦公點15km以內(nèi)和以外的雇員分為兩組当犯。劃分算法中我們將兩個標(biāo)記分別指向數(shù)組的兩頭垢村，左邊的標(biāo)記leftPtr ，向右移動嚎卫，右邊的標(biāo)記 rightPtr嘉栓，向左移動，當(dāng)leftPtr遇到比樞紐小的數(shù)據(jù)項時拓诸，繼續(xù)向右移動侵佃，當(dāng)遇到比樞紐大的數(shù)據(jù)項時就停下來，同樣當(dāng)rightPtr遇到比樞紐大的數(shù)值的時候繼續(xù)向左移動奠支，遇到比樞紐小的就停下來馋辈，然后需要交換這兩個數(shù)據(jù)項。交換之后繼續(xù)移動指針倍谜，重復(fù)上面的步驟迈螟，知道兩個標(biāo)記的值相等的時候則劃分算法完成。
接下來我們看劃分算法的java代碼
class ArrayPar {
public Long[] theArray;
private int nElems;
public ArrayPar(int max) {
theArray = new Long[max];
this.nElems = 0;
}
public void insert(Long value) {
theArray[nElems] = value;
nElems++;
}
public int partitionIt(int leftPtr, int rightPtr, long pivot) {
while (true) {
//當(dāng)leftPtr遇到比樞紐小的數(shù)據(jù)項時尔崔，繼續(xù)向右移動(即 leftPtr++)答毫，當(dāng)遇到比樞紐大的數(shù)據(jù)項時就停下來
while (leftPtr < rightPtr && theArray[leftPtr] <= pivot) //防止索引越界加上leftPtr
leftPtr++;
//當(dāng)rightPtr遇到比樞紐大的數(shù)據(jù)項時，繼續(xù)向左移動(即 rightPtr--)季春，當(dāng)遇到比樞紐大的數(shù)據(jù)項時就停下來
while (rightPtr > leftPtr && theArray[rightPtr] >= pivot)
rightPtr--;
//當(dāng)leftPtr標(biāo)記大于等于right標(biāo)記的時候結(jié)束外層循環(huán)洗搂，否則交換兩個標(biāo)記的數(shù)據(jù)項
if (leftPtr >= rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
return leftPtr;
}
/**交換數(shù)據(jù)方法*/
public void swap(int dex1, int dex2) {
long temp = theArray[dex1];
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
}
快速排序
快速排序的執(zhí)行時間為O（N*logN）級，快速排序是基于劃分算法之上的载弄，利用遞歸的思想的一種排序算法耘拇，這里我們選擇數(shù)組的最右邊的元素作為樞紐，在劃分算法完成之后侦锯，需要在之前的算法的基礎(chǔ)上加一步驼鞭，將樞紐項和右數(shù)組的起始項進行位置交換秦驯，交換后的樞紐值的順序就是最終的順序尺碰，然后在利用遞歸將劃分后的左右數(shù)組進行上述步驟。首先我們來看看快速排序的java代碼
class ArrayPar {
public Long[] theArray;
private int nElems;
public ArrayPar(int max) {
theArray = new Long[max];
this.nElems = 0;
}
public void insert(Long value) {
theArray[nElems] = value;
nElems++;
}
public int partitionIt(int leftPtr, int rightPtr, long pivot) {
int right = rightPtr;
while (true) {
//當(dāng)leftPtr遇到比樞紐小的數(shù)據(jù)項時译隘，繼續(xù)向右移動(即 leftPtr++)亲桥，當(dāng)遇到比樞紐大的數(shù)據(jù)項時就停下來
while (leftPtr < rightPtr && theArray[leftPtr] <= pivot) //防止索引越界加上leftPtr
leftPtr++;
//當(dāng)rightPtr遇到比樞紐大的數(shù)據(jù)項時，繼續(xù)向左移動(即 rightPtr--)固耘，當(dāng)遇到比樞紐大的數(shù)據(jù)項時就停下來
while (rightPtr > leftPtr && theArray[rightPtr] >= pivot)
rightPtr--;
//當(dāng)leftPtr標(biāo)記大于等于right標(biāo)記的時候結(jié)束外層循環(huán)题篷，否則交換兩個標(biāo)記的數(shù)據(jù)項
if (leftPtr >= rightPtr)
break;
else
swap(leftPtr, rightPtr);
}
swap(leftPtr,right); //最后將當(dāng)前樞紐數(shù)值放入對應(yīng)的排序位置
return leftPtr;
}
/**
* 交換數(shù)據(jù)方法
*/
public void swap(int dex1, int dex2) {
long temp = theArray[dex1];
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
/***快速排序的方法*/
public void recQuickSort(int left, int right) {
if (right - left <= 0) //這里是遞歸的基值條件，當(dāng)只有一個數(shù)據(jù)項的時候結(jié)束遞歸
return;
else {
long pivot = theArray[right]; //選擇最右邊的數(shù)據(jù)作為劃分的樞紐數(shù)據(jù)
int partition = partitionIt(left, right, pivot); //調(diào)用劃分的算法
//然后將劃分好的兩部分利用遞歸的思想進行再次劃分排序
recQuickSort(left, partition - 1);
recQuickSort(partition + 1, right);
}
}
}
下圖顯示了快速排序的過程
上面就是希爾排序算法和快速排序算法的所有內(nèi)容
