版權(quán)聲明：本文源自簡書tianma淫茵，轉(zhuǎn)載請務(wù)必注明出處：http://www.reibang.com/p/df8a9e136295
概念
快速排序是交換類排序，采用分治思想施戴，其基本原理是：通過一趟排序奖地，將待排序數(shù)組分割成獨(dú)立的兩部分间涵，其中一部分的關(guān)鍵字均比另一部分泻驮谩退疫；然后再分別對這兩部分序列遞歸進(jìn)行快速排序，從而使整個(gè)序列有序鸽素。
具體算法步驟：
- 在待排序的記錄序列中選取一個(gè)記錄作為樞軸(pivot)褒繁；
- 通過一趟排序，將所有小于樞軸的記錄都移到樞軸的左邊馍忽，將所有大于樞軸的記錄都移到樞軸的右邊棒坏，其實(shí)就是將當(dāng)前待排序序列分為兩部分，左邊部分的記錄均小于右邊部分的記錄遭笋，這樣的操作叫做partition(分割)坝冕，分割操作結(jié)束后，樞軸所處的位置就是最終排序后它所處的位置瓦呼；
- 對樞軸左右兩邊的子序列重復(fù)步驟1和2喂窟，直至所有子記錄序列只剩下一個(gè)記錄為止。
以上步驟中吵血，關(guān)鍵點(diǎn)是 1. 樞軸(pivot)的選取方式谎替； 2. 對分割操作(partition)的細(xì)節(jié)處理。
未優(yōu)化的快速排序
- 樞軸的選忍８ā：將待排序序列的第1個(gè)記錄作為樞軸；
- 分割操作 ： 分割操作中使用到了交換挫掏；
Java實(shí)現(xiàn)
// 定義接口
interface Sorter {
/**
* 將數(shù)組按升序排序
*/
int[] sort(int[] arr);
/**
* 交換數(shù)組arr中的第i個(gè)位置和第j個(gè)位置的關(guān)鍵字
*/
default void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 未優(yōu)化的快速排序
class QuickSorter implements Sorter {
@Override
public int[] sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
return arr;
}
/**
* 對數(shù)組arr[low...high]的子序列作快速排序侦另，使之有序
*/
protected void quickSort(int[] arr, int low, int high) {
int pivotLoc; // 記錄樞軸(pivot)所在位置
if (low < high) {
pivotLoc = partition(arr, low, high); // 將arr[low...high]一分為二,并返回樞軸位置
quickSort(arr, low, pivotLoc - 1);// 遞歸遍歷arr[low...pivotLoc-1]
quickSort(arr, pivotLoc + 1, high); // 遞歸遍歷arr[pivotLoc+1...high]
}
}
/**
* 在arr[low...high]選定pivot=arr[low]作為樞軸（中間位置），將arr[low...high]分成兩部分尉共，
* 前半部分的子序列的記錄均小于pivot褒傅，后半部分的記錄均大于pivot;最后返回pivot的位置
*/
protected int partition(int[] arr, int low, int high) {
int pivot;
pivot = arr[low]; // 將arr[low]作為樞軸
while (low < high) { // 從數(shù)組的兩端向中間掃描 // A
while (low < high && arr[high] >= pivot) { // B
high--;
}
swap(arr, low, high); // 將比樞軸pivot小的元素交換到低位 // C
while (low < high && arr[low] <= pivot) { //D
low++;
}
swap(arr, low, high); // 將比樞軸pivot大的元素交換到高位 // E
}
return low; // 返回一趟下來后樞軸pivot所在的位置
}
}
演示
為了方便演示，我對上面代碼中的分割操作partition方法的代碼進(jìn)行了標(biāo)注（分別標(biāo)注為 A,B,C,D,E）袄友。
對于待排序序列 {5, 1, 9, 3, 7, 4, 8, 6, 2}殿托，我們來演示其第一趟排序過程：
low = 0, high = 8, pivot = arr[low] = 5;
- A處，low = 0, high = 8, low<high剧蚣，進(jìn)行A循環(huán)支竹；
- B處旋廷，high的值不斷遞減，直至arr[high] = 2 小于pivot礼搁，跳出B循環(huán)：
pivot
↓
5 1 9 3 7 4 8 6 2
↑ ↑
low high
- C處饶碘，執(zhí)行l(wèi)ow和high的元素交換：
pivot
↓
2 1 9 3 7 4 8 6 5
↑ ↑
low high
- D處，low的值不斷遞增馒吴，直至arr[low] = 9 大于 pivot扎运，跳出D循環(huán):
pivot
↓
2 1 9 3 7 4 8 6 5
↑ ↑
low high
- E處，執(zhí)行l(wèi)ow和high的元素交換：
pivot
↓
2 1 5 3 7 4 8 6 9
↑ ↑
low high
- A處饮戳，low =2, high = 8, low < high豪治，繼續(xù)循環(huán)A；
- B處扯罐，high的值不斷遞減鬼吵，直至arr[high] = 4 小于pivot，跳出B循環(huán)：
pivot
↓
2 1 5 3 7 4 8 6 9
↑ ↑
low high
- C處篮赢，執(zhí)行l(wèi)ow和high的元素交換：
pivot
↓
2 1 4 3 7 5 8 6 9
↑ ↑
low high
- D處齿椅，low的值不斷遞增，直至arr[low] = 7 大于 pivot启泣，跳出D循環(huán)：
pivot
↓
2 1 4 3 7 5 8 6 9
↑ ↑
low high
- E處涣脚，執(zhí)行l(wèi)ow和high的元素交換：
pivot
↓
2 1 4 3 5 7 8 6 9
↑ ↑
low high
- A處，low = 4寥茫， high = 5遣蚀， low < high， 繼續(xù)循環(huán)A：
- B處纱耻，high不斷遞減芭梯，直至high=4 等于 low，不滿足 low < high弄喘，跳出B循環(huán)：
pivot
↓
2 1 4 3 5 7 8 6 9
↑
low
high
- 因?yàn)閘ow和high已經(jīng)重合玖喘，所以在接下來的C、D蘑志、E操作中序列均未發(fā)生變化
- A處累奈，low=4, high = 4, 不滿足 low < high, 跳出A循環(huán)，最后返回low=4急但，即為pivot所在位置澎媒；
所以第1趟排序下來之后，序列會變成 {2, 1, 4, 3, 5, 7, 8, 6, 9}波桩；然后再對子序列{2, 1, 4, 3} 和 {7, 8, 6, 9} 做同樣的操作即可完成整個(gè)排序戒努。
對于partition方法中的low和high，可以這樣理解：在low左邊的記錄都都小于等于樞軸pivot镐躲，在high右邊的記錄都大于等于樞軸pivot储玫，那么當(dāng)low和high重合時(shí)侍筛，則表示已經(jīng)分割完畢，重合的位置（即low的值）就是樞軸pivot的位置缘缚。
快速排序的優(yōu)化
?
(1) 樞軸的選取方式的優(yōu)化：
樞軸的選取方式有：(1) 固定位置選裙窗省；(2) 隨機(jī)位置選惹疟酢窝爪； (3) 三值取中法 等
固定位置選取：選取當(dāng)前序列的第一個(gè)元素或者最后一個(gè)元素作為樞軸齐媒，上面的算法的樞軸選取方式即為固定位置選取蒲每。該方法不是一個(gè)好的選取方案，因?yàn)楫?dāng)整個(gè)序列有序時(shí)喻括，每次分割(partition)操作只會將待排序序列減1邀杏，此時(shí)為最壞情況，算法復(fù)雜度淪為O(n^2)唬血。然而望蜡，在待排序的序列中局部有序是相當(dāng)常見的，所以固定位置選取樞軸不是一種好的選擇拷恨。
隨機(jī)位置選炔甭伞：隨機(jī)選取當(dāng)前待排序序列的任意記錄作為樞軸。由于采取隨機(jī)腕侄，所以時(shí)間性能要強(qiáng)于固定位置選取小泉。
三值取中法： 待排序序列的前(第一個(gè)位置)、中(中間位置)冕杠、后(最后一個(gè)位置)三個(gè)記錄中的中間值(按大小排序)作為樞軸微姊，比如:
9 1 7 5 2 8 6 3 4
↑ ↑ ↑
low mid high
前 中 后
由于 9 > 4 > 2； 因此將4作為此次分割(partition)操作的樞軸分预。
三值取中操作后兢交，整個(gè)序列變?yōu)椋?/p>
4 1 7 5 2 8 6 3 9
↑ ↑ ↑
low mid high
前 中 后
三值取中本質(zhì)上就是隨機(jī)位置選取，但是由于隨機(jī)位置選取過程中需要用到隨機(jī)種子來產(chǎn)生隨機(jī)數(shù)噪舀，而三值取中不需要魁淳，所以三值取中要優(yōu)于隨機(jī)位置選取。
所以優(yōu)化樞軸的選取方式時(shí)与倡，我們選擇三值取中的方式。
(2) 優(yōu)化小數(shù)組時(shí)的排序方案：
當(dāng)局部排序數(shù)組長度較小時(shí)昆稿，采用插入排序纺座，而非快速排序，因?yàn)殚L度分割到夠小后溉潭，繼續(xù)分割的效率要低于直接插入排序净响。
(3) 略去不必要的交換：
略去不必要的交換少欺，將交換操作改為替換操作。
因?yàn)榻粨Q操作需要進(jìn)行3次賦值操作馋贤，而替換操作只需要進(jìn)行1次賦值操作赞别。
Java實(shí)現(xiàn)
// 優(yōu)化的快速排序
class OptimizedQuickSorter extends QuickSorter {
/**
* 插入排序最大數(shù)組長度值
*/
private static final int MAX_LENGTH_INSERT_SORT = 7;
/**
* 對數(shù)組arr[low...high]的子序列作快速排序，使之有序
*/
@Override
protected void quickSort(int[] arr, int low, int high) {
int pivotLoc; // 記錄樞軸(pivot)所在位置
if ((high - low + 1) > MAX_LENGTH_INSERT_SORT) {
// 待排序數(shù)組長度大于臨界值配乓，則進(jìn)行快速排序
pivotLoc = partition(arr, low, high); // 將arr[low...high]一分為二,并返回樞軸位置
quickSort(arr, low, pivotLoc - 1);// 遞歸遍歷arr[low...pivotLoc-1]
quickSort(arr, pivotLoc + 1, high); // 遞歸遍歷arr[pivotLoc+1...high]
} else {
// 2. 優(yōu)化小數(shù)組時(shí)的排序方案仿滔，將快速排序改為插入排序
insertSort(arr, low, high); // 對arr[low...high]子序列進(jìn)行插入排序
}
}
/**
* 在arr[low...high]中利用三值取中選取樞軸(pivot)，將arr[low...high]分成兩部分犹芹，
* 前半部分的子序列的記錄均小于pivot崎页，后半部分的記錄均大于pivot;最后返回pivot的位置
*/
@Override
protected int partition(int[] arr, int low, int high) {
int pivot;
pivot = medianOfThree(arr, low, high); // 1. 優(yōu)化排序基準(zhǔn)，使用三值取中獲取中值
while (low < high) { // 從數(shù)組的兩端向中間掃描 // A
while (low < high && arr[high] >= pivot) { // B
high--;
}
// swap(arr, low, high); // 將比樞軸pivot小的元素交換到低位
arr[low] = arr[high]; // 3. 優(yōu)化不必要的交換腰埂，使用替換而不是交換 // C
while (low < high && arr[low] <= pivot) { // D
low++;
}
// swap(arr, low, high); // 將比樞軸pivot大的元素交換到高位
arr[high] = arr[low]; // 3. 優(yōu)化不必要的交換飒焦，使用替換而不是交換 // E
}
arr[low] = pivot; // F
return low; // 返回一趟下來后樞軸pivot所在的位置
}
/**
* 通過三值取中(從arr[low...high]子序列中)獲取樞軸pivot的值，讓arr[low]變成中值;并返回計(jì)算的樞軸(pivot)
*/
private int medianOfThree(int[] arr, int low, int high) {
int mid = low + ((high - low) >> 1); // mid = low + (high-low)/2, 中間元素下標(biāo)
// 使用三值取中得到樞軸
if (arr[low] > arr[high]) { // 目的：讓arr[low] <= arr[high]
swap(arr, low, high);
}
if (arr[mid] > arr[high]) { // 目的：讓arr[mid] <= arr[high]
swap(arr, mid, high);
}
if (arr[mid] > arr[low]) { // 目的： 讓arr[low] >= arr[mid]
swap(arr, low, mid);
}
// 經(jīng)過上述變化屿笼，最終 arr[mid]<=arr[low]<=arr[high]牺荠，則arr[low]為中間值
return arr[low];
}
/**
* 對子序列arr[low...high]進(jìn)行插入排序
*/
private void insertSort(int[] arr, int low, int high) {
int i, j;
int tmp;
for (i = low + 1; i <= high; i++) { // 從下標(biāo)low+1開始遍歷,因?yàn)橄聵?biāo)為low的已經(jīng)排好序
if (arr[i] < arr[i - 1]) {
// 如果當(dāng)前下標(biāo)對應(yīng)的記錄小于前一位記錄,則需要插入,否則不需要插入，直接將記錄數(shù)增加1
tmp = arr[i]; // 記錄下標(biāo)i對應(yīng)的元素
for (j = i - 1; j >= low && arr[j] > tmp; j--) {
arr[j + 1] = arr[j]; // 記錄后移
}
arr[j + 1] = tmp; // 插入正確位置
}
}
}
}
演示
為了方便演示驴一，我對上面代碼中的分割操作partition方法的代碼仍然進(jìn)行了標(biāo)注（分別標(biāo)注為 A,B,C,D,E,F）休雌。
對于待排序序列 {5, 1, 9, 3, 7, 4, 8, 6, 2}，我們來演示其第一趟排序過程：
low = 0蛔趴， high = 8挑辆， high-low+1=9 > MAX_LENGTH_INSERT_SORT， 所以需要進(jìn)行快速排序孝情，接下來進(jìn)行分割(partition)操作鱼蝉；
- 此時(shí)待排序序列：
5 1 9 3 7 4 8 6 2
↑ ↑
low high
- 三值取中前：
5 1 9 3 7 4 8 6 2
↑ ↑ ↑
low mid high
三值取中后：
pivot
↓
5 1 9 3 2 4 8 6 7
↑ ↑ ↑
low mid high
pivot = 5；
- A處箫荡，low = 0, high = 8, low < high, 進(jìn)行A循環(huán)魁亦；
- B處，high的值不斷遞減羔挡，直至arr[high] = 4 小于pivot洁奈，跳出B循環(huán)：
5 1 9 3 2 4 8 6 7
↑ ↑
low high
- C處，arr[low] = arr[high]绞灼，將低位的值替換成高位的值：
4 1 9 3 2 4 8 6 7
↑ ↑
low high
- D處利术，low的值不斷遞增，直至arr[low] = 9 大于 pivot低矮，跳出D循環(huán):
4 1 9 3 2 4 8 6 7
↑ ↑
low high
- E處印叁，arr[high] = arr[low]， 將高位的值替換成低位的值：
4 1 9 3 2 9 8 6 7
↑ ↑
low high
- A處，low = 2, high = 5, low < high, 進(jìn)行A循環(huán)轮蜕；
- B處昨悼，high的值不斷遞減，直至arr[high] = 2 小于pivot跃洛，跳出B循環(huán)：
4 1 9 3 2 9 8 6 7
↑ ↑
low high
- C處率触，arr[low] = arr[high]，將低位的值替換成高位的值：
4 1 2 3 2 9 8 6 7
↑ ↑
low high
- D處汇竭，low的值不斷遞增葱蝗，直至low = 4, high = 4, low == high，不滿足 low<high韩玩，跳出D循環(huán):
4 1 2 3 2 9 8 6 7
↑
low
high
- 因?yàn)閘ow和high已經(jīng)重合垒玲，所以在接下來的E操作中序列未發(fā)生變化；
- A處找颓，low=4, high = 4, 不滿足 low < high, 跳出A循環(huán)合愈；
- F處， arr[low] = pivot:
4 1 2 3 5 9 8 6 7
↑
low
high
- 最后返回low = 4击狮，即為pivot所在的位置佛析。
所以這趟排序下來之后，序列會變成 {4 1 2 3 5 9 8 6 7}彪蓬；然后再對子序列{4, 1, 2, 3} 和 {9, 8, 6, 7} 做同樣的操作即可完成整個(gè)排序寸莫。
復(fù)雜度
時(shí)間復(fù)雜度：
時(shí)間復(fù)雜度為O(nlogn)，在對快速排序進(jìn)行各種細(xì)節(jié)性的優(yōu)化后档冬，快速排序的性能大大提高膘茎，在一般條件下超越了其它排序方法，故得此名酷誓。
空間復(fù)雜度：
就空間復(fù)雜度來說披坏，主要是遞歸造成的棧空間的使用盐数，最好情況棒拂，遞歸的深度為log2n，其空間復(fù)雜度也就為O(logn)玫氢，最壞情況帚屉，需要進(jìn)行n‐1遞歸調(diào)用，其空間復(fù)雜度為O(n)漾峡，平均情況攻旦，空間復(fù)雜度也為O(logn)。
?
參考鏈接：
常見排序算法 - 快速排序 (Quick Sort)
三種快速排序以及快速排序的優(yōu)化
