快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較度液。在最壞狀況下則需要 Ο(n2) 次比較湾碎，但這種狀況并不常見宙攻。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快介褥，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來座掘。
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用呻顽。本質(zhì)上來看雹顺，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
快速排序的名字起的是簡單粗暴廊遍，因為一聽到這個名字你就知道它存在的意義嬉愧，就是快，而且效率高喉前！它是處理大數(shù)據(jù)最快的排序算法之一了没酣。雖然 Worst Case 的時間復雜度達到了 O(n2)王财，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時間復雜度為 O(n logn) 的排序算法表現(xiàn)要更好裕便，可是這是為什么呢绒净，我也不知道。好在我的強迫癥又犯了偿衰，查了 N 多資料終于在《算法藝術(shù)與信息學競賽》上找到了滿意的答案：
- 快速排序的最壞運行情況是 O(n2)挂疆，比如說順序數(shù)列的快排。但它的平攤期望時間是 O(nlogn)下翎，且 O(nlogn) 記號中隱含的常數(shù)因子很小缤言，比復雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以视事，對絕大多數(shù)順序性較弱的隨機數(shù)列而言胆萧，快速排序總是優(yōu)于歸并排序。
1. 算法步驟
- 從數(shù)列中挑出一個元素俐东，稱為 "基準"（pivot）;
- 重新排序數(shù)列跌穗，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）虏辫。在這個分區(qū)退出之后蚌吸，該基準就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作砌庄；
- 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序套利；
quickSort.gif
2.代碼
#include <stdio.h>
void
sort(int *data, int left, int right)
{
if (left >= right)
return;
int i = left;
int j = right;
int key = data[left];
while (i < j) {
while (i < j && key <= data[j]) {
j --;
}
data[i] = data[j];
while (i < j && key >= data[i]) {
i ++;
}
data[j] = data[i];
}
data[i] = key;
sort(data, left, i - 1);
sort(data, i + 1, right);
}
int
quick_sort(int *data, int length)
{
sort(data, 0, length - 1);
}
int
main()
{
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = (int) sizeof(arr) / sizeof(*arr);
quick_sort(arr, len);
int i;
for (i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
轉(zhuǎn)載于菜鳥教程
2020.10.29 10:24 深圳
