概念
快速排序（英語：Quick Sort）芥吟，又稱分區(qū)交換排序（partition-exchange sort）澎灸，簡稱快排蛹头，一種排序算法顿肺，最早由東尼·霍爾提出戏溺。在平均狀況下，排序n個項目要 O(nlog n)（大O符號）次比較挟冠。在最壞狀況下則需要 O(n^2 ) 次比較，但這種狀況并不常見袍睡。事實上知染，快速排序（nlogn）通常明顯比其他算法更快，因為它的內部循環(huán)(inner loop)可以在大部分的架構上很有效率地達成斑胜。
解題思路
通過一趟排序將要排序的數據分割成獨立的兩部分控淡，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序止潘，整個排序過程可以遞歸進行掺炭，以此達到整個數據變成有序序列∑敬鳎快速排序采
用了分治法來解決問題涧狮。
運行過程
1、從序列中挑出一個元素么夫，稱為“基準”（pivot）者冤。一般是選取序列的第一個元素。
（假設每次選擇0位置的元素為軸點元素）2档痪、重新排序數列涉枫，
所有比基準值小的元素擺放在基準前面
所有比基準值大的元素擺在基準的后面（相同的數可以到任一邊）。
在這個分區(qū)結束之后腐螟，該基準就處于數列的中間位置愿汰。這個稱為分區(qū)（partition）操作。
3乐纸、遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序衬廷。
4、直到序列的大小是0或1汽绢，也就是所有元素都已經被排序好了泵督，遞歸結束。
代碼
Java
public class QuickSort {
public int[] array;
public void sort() {
sort(0,array.length);
}
private void sort(int begin ,int end){
if (end - begin < 2) return ;
int mid = pivotIndex(begin,end);
sort(begin,mid);
sort(mid + 1,end);
}
private int pivotIndex(int begin, int end){
// 隨機選擇一個元素跟begin位置進行交換
swap(begin,begin + (int) (Math.random() * (end - begin)));
// 備份begin位置的元素
int pivot = array[begin];
// end指向最后一個元素
end--;
while (begin < end){
while (begin < end){
if (pivot < array[end]){ // 右邊元素 > 軸點元素
end--;
}else { // 右邊元素 <= 軸點元素
array[begin++] = array[end];
break;
}
}
while (begin < end){
if (pivot > array[end]){ // 左邊元素 < 軸點元素
begin++;
}else { // 左邊元素 >= 軸點元素
array[end --] = array[begin];
break;
}
}
}
array[begin] = pivot;
return begin;
}
protected void swap(int i1, int i2) {
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
}
性能
-
在軸點左右元素數量比較均勻的情況下庶喜，同時也是最好的情況
OT(n)= 2* T(n/2) + 0(n) = 0(nlogn)
如果軸點左右元素數量極度不均勻小腊，最壞情況
0 T(n)= T(n- 1)+ 0(n)= 0(n2)為了降低最壞情況的出現概率，一般采取的做法是
隨機選擇軸點元素最好久窟、平均時間復雜度: 0(nlogn)
最壞時間復雜度: 0(n2)
由于遞歸調用的緣故,空間復雜度: 0(logn)
屬于不穩(wěn)定排序
參考文章：
經典排序算法（2）——快速排序算法詳解
《戀上數據結構與算法第二季》
