1. 一種簡單的快速排序
快速排序最重要的就是partition函數(shù)耗美，即選定某一個數(shù)后徙融，使得所有小于該數(shù)的數(shù)字都在其左側(cè)捕犬，大于該數(shù)的數(shù)字都在其右側(cè)舍扰。本節(jié)給出的算法過程如下：
我們將需要劃分的目標(biāo)區(qū)間定位[l, u]。
首先給定目標(biāo)值t = x[l]侣诵。我們需要重新組織x[l...u]痢法，使得所有小于t的元素都在m的一端狱窘，所有大于t的元素在m的另一端。
初始時m = l财搁，我們將i從l+1一直遍歷到u蘸炸，代碼在檢測第i個元素時必須考慮兩種情況。如果x[i]>=t妇拯，那么一切正常幻馁，不變式為真；如果x[i]<t越锈，可以通過使m增加1（指向小元素的新位置）重新獲得不變式，然后交換x[i]和x[m]膘滨。
完整代碼如下：
void qsort1(int nums[], int l, int u) {
if (l < u) {
int m = l;
for (int i = l + 1; i <= u; i++) {
int num = nums[i];
if (num < nums[l]) {
swap(nums[++m], nums[i]);
}
}
swap(nums[m], nums[l]);
myqsort(nums, l, m - 1);
myqsort(nums, m + 1, u);
}
}
2. 更好的幾種快速排序
qsort1函數(shù)能夠快速完成對隨機整數(shù)數(shù)組的排序甘凭，但是在非隨機的輸入上它的性能如何呢？我們不妨采用一種極端的情況：n個相同元素組成的數(shù)組火邓，對于這種輸入丹弱，插入排序的性能非常好：每個元素需要移動的距離都為0；但是qsort1函數(shù)的性能卻非常糟糕铲咨。n-1次劃分中每次劃分都需要O(n)時間來去掉一個元素躲胳，所以總的運行時間為O(n2)。使用雙向劃分可以避免這種情況纤勒。
下標(biāo)i和j初始化為待劃分數(shù)組的兩端坯苹。主循環(huán)中有兩個內(nèi)循環(huán)，第一個內(nèi)循環(huán)將i向右移過小元素摇天，遇到大元素時停止粹湃；第二個內(nèi)循環(huán)將j向左移過大元素，遇到小元素時停止泉坐。然后主循環(huán)測試這兩個下標(biāo)是否交叉并交換它們的值为鳄。這樣做雖然交換的次數(shù)增加了，但卻將所有元素都相同的最壞情況變成了差不多需要nlog2n次比較的最好情況腕让，實現(xiàn)代碼如下：
void qsort2(int nums[], int l, int u) {
if (l < u) {
int i = l + 1;
int j = u;
int t = nums[l];
while (i <= j) {
while (i <= u && nums[i] < t) {
i++;
}
while (nums[j] > t) {
j--;
}
if (i <= j) {
swap(nums[i], nums[j]);
}
}
swap(nums[l], nums[j]);
qsort2(nums, l, j - 1);
qsort2(nums, j + 1, u);
}
}
到目前為止我們看到的快速排序都是圍繞數(shù)組的第一個元素進行劃分的孤钦。對于隨機輸入，這樣做沒問題纯丸；但對于某些常見輸出偏形，這種做法需要的時間和空間都偏多。例如液南，雖然數(shù)組已經(jīng)按升序排好了壳猜，那么它就會先圍繞最小的元素進行劃分，然后是第二小的元素滑凉，以此類推统扳，總共需要O(n2)的時間喘帚。隨機選擇劃分元素就可以得到好得多的性能，我們通過把x[l]與x[l...u]中的一個隨機項相交換來實現(xiàn)這一點：
swap(l, randint(l, u));
我們的快速排序花費了大量的時間來排序很小的子數(shù)組咒钟。如果用插入排序之類的簡單方法來排序這些很小的子數(shù)組吹由，程序的速度會很快。我們將qsort2中的第一個if語句改為：
if (u - l >= cutoff)
其中cutoff是一個小整數(shù)朱嘴。程序結(jié)束后倾鲫，數(shù)組并不是有序的，而是被組合成一塊一塊隨機排列的值萍嬉，并且滿足這樣的條件：某一塊中的元素小于它右邊任何塊中的元素乌昔。我們必須通過另一種排序算法對塊的內(nèi)部進行排序。由于數(shù)組是幾乎有序的壤追，因此插入排序比較適用磕道。
