什么是快速排序子巾？
快速排序由C. A. R. Hoare在1962年提出。
它的基本思想是:
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分沐扳，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小.
然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列袋毙。
實現(xiàn)思路：
1．先從數(shù)列中取出一個數(shù)作為基準數(shù)。
2．分區(qū)過程冗尤，將比這個數(shù)大的數(shù)全放到它的右邊听盖，小于或等于它的數(shù)全放到它的左邊胀溺。
3．再對左右區(qū)間重復第二步，直到各區(qū)間只有一個數(shù)皆看。
過程圖解：
如上圖所示仓坞，經(jīng)過第一輪劃分以后，數(shù)組以32位界限被分成了兩部分腰吟，左邊的都比32小扯躺，右邊的都比32大，接下來只要對兩個分區(qū)重復上述步驟蝎困，直到每個分區(qū)都只有一個數(shù)據(jù)位置录语。
代碼實現(xiàn)：
/**
* @param s
* @param l
* @param r
*/
static void quickSort(int s[], int l, int r) {
if (l < r) {
int i = l, j = r, x = s[l];
while (i < j) {
while (i < j && s[j] >= x)
// 從右向左找第一個小于x的數(shù)
j--;
if (i < j)
s[i++] = s[j];
while (i < j && s[i] < x)
// 從左向右找第一個大于等于x的數(shù)
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 遞歸調(diào)用
quickSort(s, i + 1, r);
}
}
總結(jié)：
時間復雜度：O（n*lgn）
最壞：O（n^2）
空間復雜度：O（n*lgn）
穩(wěn)定性：不穩(wěn)定。
快速排序是一種排序算法禾乘，對包含n個數(shù)的輸入數(shù)組澎埠，平均時間為O（nlgn），最壞情況是O（n^2）始藕。
通常是用于排序的最佳選擇蒲稳。因為，基于比較的排序伍派，最快也只能達到O（nlgn）江耀。
