快速排序（Quick Sort）
一、概念
- 從序列中選擇一個(gè)
軸點(diǎn)元素（pivot）,假設(shè)每次選擇0位置的元素為軸點(diǎn)元素。
image
- 利用
pivot將序列分割成2個(gè)子序列，將小于pivot的元素放在pivote前面（左側(cè)），將大于pivot的元素放在pivot后面（右側(cè)），等于pivot的元素放在哪邊都可以。
image
- 對(duì)子序列進(jìn)行上一步操作，直到不能再分割（子序列中只剩下
1個(gè)元素）。
image
- 快速排序的本質(zhì)：逐漸將每個(gè)元素都轉(zhuǎn)換成軸點(diǎn)元素。
二、軸點(diǎn)構(gòu)造
- 將
6作為軸點(diǎn)，備份一份。
image
- 從
右邊（end）開(kāi)始掃描數(shù)組。 - 掃描
7，大于6a，執(zhí)行end--即可。
image
- 掃描
5，小于6a，用5覆蓋6a的位置，begin++。
image
- 下一步，從
左邊（begin）繼續(xù)掃描。 - 掃描
8a，大于6a，用8a覆蓋5的位置，end--。
image
- 下一步，從
右邊（end）繼續(xù)掃描 - 掃描
9，大于6a，執(zhí)行end--，不做其他操作。
image
- 掃描
4，小于6a，用4覆蓋8a的位置，begin++。
image
- 掃描
8b，大于6a，用8b覆蓋4的位置，end--。
image
- 掃描
6b，等于6a，用6b覆蓋8b的位置，begin++。
image
- 掃描
2，小于6a，begin++。
image
- 當(dāng)發(fā)現(xiàn)
begin和end重疊，則軸點(diǎn)構(gòu)造完成。將備份的6a，覆蓋6b的位置。
image
三、代碼實(shí)現(xiàn)
public class QuickSort<T extends Comparable<T>> extends Sort<T> {
@Override
protected void sort() {
sort(0, array.length);
}
/**
* 對(duì) [begin, end) 范圍的元素進(jìn)行快速排序
* @param begin
* @param end
*/
private void sort(int begin, int end) {
if (end - begin < 2) return; //至少有兩個(gè)元素才執(zhí)行快速排序
// 確定軸點(diǎn)位置 O(n)，并進(jìn)行一次快速排序
int mid = pivotIndex(begin, end);
// 對(duì)子序列進(jìn)行快速排序
sort(begin, mid);
sort(mid + 1, end);
}
/**
* 構(gòu)造出 [begin, end) 范圍的軸點(diǎn)元素，并進(jìn)行一次快速排序
* @return 軸點(diǎn)元素的最終位置
*/
private int pivotIndex(int begin, int end) {
// 為了降低最壞情況(O(n^2)的時(shí)間復(fù)雜度)的出現(xiàn)概率，隨機(jī)選擇一個(gè)元素跟begin位置進(jìn)行交換
swap(begin, begin + (int)(Math.random() * (end - begin)));
// 備份begin位置的元素
T pivot = array[begin];
// end指向最后一個(gè)元素
end--;
// 如果begin == end 則退出排序
while (begin < end) {
while (begin < end) {
if (cmp(pivot, array[end]) < 0) { // 右邊元素 > 軸點(diǎn)元素
end--; // 只位移，不進(jìn)行元素交換
} else { // 右邊元素 <= 軸點(diǎn)元素
array[begin++] = array[end];
break; //執(zhí)行完一次操作后，需要掉頭，所以執(zhí)行一個(gè)break
}
}
while (begin < end) {
if (cmp(pivot, array[begin]) > 0) { // 左邊元素 < 軸點(diǎn)元素
begin++;
} else { // 左邊元素 >= 軸點(diǎn)元素
array[end--] = array[begin];
break; // 通過(guò)兩個(gè)break，能實(shí)現(xiàn)兩個(gè)while交替執(zhí)行。
}
}
}
// 將軸點(diǎn)元素放入最終的位置
array[begin] = pivot;
// 返回軸點(diǎn)元素的位置
return begin;
}
}
復(fù)制代碼
- 在當(dāng)前算法，如果序列中的
元素a與軸點(diǎn)元素相等，則會(huì)將軸點(diǎn)元素與元素a替換位置。
image
- 如果
元素a與軸點(diǎn)元素相等時(shí)，不進(jìn)行替換，那么最終得到的數(shù)組會(huì)非常不平衡（黃色軸點(diǎn)在數(shù)組中的位置），導(dǎo)致出現(xiàn)最壞時(shí)間復(fù)雜度O(n^2)。
image
四、時(shí)間復(fù)雜度
- 在軸點(diǎn)左右元素?cái)?shù)量比較均勻的情況下，同時(shí)也是最好的情況，時(shí)間復(fù)雜度是
O(nlogn)。 - 如果軸點(diǎn)左右元素?cái)?shù)量極度不均勻，最壞情況是
O(n^2)。
image
- 為了降低最壞情況的出現(xiàn)概率，一般采取的做法是
隨機(jī)選擇軸點(diǎn)元素。 - 由于遞歸調(diào)用的緣故，空間復(fù)雜度是：
O(logn)。 - 快速排序?qū)儆?code>不穩(wěn)定排序。
