▼ 簡介
快速排序（Quicksort）是對冒泡排序的一種改進。
快速排序由C. A. R. Hoare在1962年提出郭赐。它的基本思想是：通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小确沸，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序捌锭，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列罗捎。
▼ 原理
一趟快速排序的算法是：
1）設置兩個變量i观谦、j，排序開始的時候：i=0桨菜，j=N-1豁状；
2）以第一個數(shù)組元素作為基準點。
3）從j開始向前搜索倒得，即由后開始向前搜索(j--)泻红，找到第一個小于Ai的值A[j]，將值與A[j]交換霞掺；
4）從i開始向后搜索谊路，即由前開始向后搜索(i++)，找到第一個大于A[j]（此時基準點）的A[i]菩彬，將A[j]與A[i]交換缠劝；
5）重復第3步
6）重復第3、4挤巡、5步剩彬，直到i=j酷麦； (3,4步中矿卑，沒找到符合條件的值，即3中A[j]不小于key,4中A[j]不大于key的時候改變j沃饶、i的值母廷，使得j=j-1轻黑，i=i+1，直至找到為止琴昆。找到符合條件的值氓鄙，進行交換的時候i， j指針位置不變业舍。另外抖拦，i==j這一過程一定正好是i+或j-完成的時候，此時令循環(huán)結束）舷暮，到此找到基準點的下標态罪，作為分治下標。
7重復1-6步驟遞歸排序前半部分
8 重復1-6步驟遞歸排序后半部分
▼ 代碼
<pre>
public static void sort(int a[], int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = a[i]; // 用子表的第一個記錄做基準
while (i < j) { // 從表的兩端交替向中間掃描
while (i < j && a[j] >= index)
j--;
if (i < j)
a[i++] = a[j];// 用比基準小的記錄替換低位記錄
while (i < j && a[i] < index)
i++;
if (i < j) // 用比基準大的記錄替換高位記錄
a[j--] = a[i];
}
a[i] = index;// 將基準數(shù)值替換回 a[i]
sort(a, low, i - 1); // 對低子表進行遞歸排序
sort(a, i + 1, hight); // 對高子表進行遞歸排序
}
</pre>
▼ 屬性
穩(wěn)定度：不穩(wěn)定
最差時間分析：O(n2)
平均時間復雜度： O(n*log2n)
空間復雜度：O(log2n)-O(n)
