演算法初步——快速排序
上一節中我們講到冒泡排序的演算法時間複雜度為O(N^2)，這是一個比較大的時間複雜度，在演算法執行上效率很低。於是我們就想一想有沒有既不浪費空間又能提高效率的演算法呢，當然，我們找到了一個更為常用的排序演算法——快速排序。「快速排序」光聽這個名字是不是就很高端呢，接下來我們來看一看該演算法如何實現。
假設我們對「6 1 2 7 9 3 4 5 10 8」這10個數進行排序。我們首先要選定一個數作為基準數。我們一般可以選這串數字的第一個數為基準數，緊接著我們要把比6小的數全部移動到6的左邊，而比6大的數我們全部移動到6的右邊，結果為「3 1 2 5 4 6 9 7 10 8；這時候你一定會好奇我們如何將原來的那串數字變成現在這個樣子的，接下來看清楚：我們需要兩個變數我們可以稱這兩個變數為「哨兵i」和「哨兵j」，兩個哨兵從兩端進行探測，但我們有個原則：哨兵j的級別比哨兵i的級別高，所以它永遠先走。我們將哨兵j向前遍歷找到第一個比基準數（也就是6）小的數，接下來我們就要讓哨兵i向後找到第一個比基準數大的數，將他倆交換；接著哨兵j繼續行動探測下一個比基準數小的數，隨後哨兵i出擊進行探測……當我們發現兩個哨兵要接頭時，我們將接頭位置的數和基準數進行交換（當我們要排序的數串里數字的個數為奇數時，我們則把哨兵i和基準數交換，實際無論是奇數還是偶數，我們只需要將哨兵i和基準數交換即可），這樣我們的基準數6就到達了它應該在的位置，接下來進行第二輪的探測。每一輪探測我們將會確定一個基準數的位置，當所有基準數的位置我們都確定之後，我們的排序工作也就完成了。
快速排序之所以比冒泡排序的效率高，是因為冒泡排序處理數據是連續的，而快速排序處理數據是跳躍式的。總的比較和交換次數變少我們的速度自然就變快了。經過我們分析可以知道，快速排序的演算法時間複雜度為O(NlogN)。快速排序的原理其實是二分法的應用，我們有機會再詳談。
#include<iostream> using namespace std; int a[101], n; void quicksort(int left, int right) { int t, temp, i, j; if (left > right) return; temp = a[left];//用temp儲存下我們的基準數 i = left; j = right;//定義兩個哨兵 while (i != j)//開始探測 { //順序很重要，我們先從後往前探測 while (a[j] >= temp && i < j) j--; //再從前往後探測 while (a[i] <= temp && i < j) i++; //交換過程 if (i < j) { t = a[j]; a[j] = a[i]; a[i] = t; } } //將基準數歸位 a[left] = a[i]; a[i] = temp; quicksort(left, i - 1);//接著處理基準數左側的數據 quicksort(i + 1, right);//處理基準數右側的數據 return; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } quicksort(1, n); for (int i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; return 0; }
