快速排序基本特性 時間復雜度：O（n*lgn） 最壞：O（n^2） 空間復雜度：最好情況下：O（lgn），最壞情況：O(n)，平均情況：O(lgn) 不穩定。 關於快速排序的空間復雜度，謝謝@命運他爹 同學指正。詳述一下。 快速排序由於每次遞歸的時候會占用一個空間返回中間數位置，所以一次遞歸的空間復雜度為O(1)。 最好情況和平均情況下的遞歸深度為O(lgn)，相應的空間復雜度就是O(lgn) 最壞情況下的遞歸深度為O(n)，空間復雜度為O(n)。 算法 QUICKSORT(A, p, r) if p < r then q ← PARTITION(A, p, r) //關鍵 QUICKSORT(A, p, q - 1) QUICKSORT(A, q + 1, r) PARTITION(A, p, r) x ← A[r] i ← p - 1 for j ← p to r - 1 do if A[j] ≤ x then i ← i + 1 exchange A[i] <-> A[j] exchange A[i + 1] <-> A[r] return i + 1 示例 待排序數組：7 3 5 9 8 5 1 10 4 6 clipboard 一趟排序過程分析： 1 quicksort一趟排序過程 源碼 類聲明 class BaseSort { public: BaseSort() { } virtual void sort() = 0; }; class QuickSort : public BaseSort { public: QuickSort(int Array[], int len) : BaseSort() { this->Array = Array; this->len = len; } void sort(); private: int partition(int Array[], int start, int end); void quicksort(int Array[], int start, int end); private: int* Array; int len; }; 相關成員函數實現 void QuickSort::sort() { quicksort(Array, 0, len-1); } void QuickSort::quicksort(int Array[], int start, int end) { if ( start < end ) { int mid = this->partition(Array, start, end); if ( start < mid - 1 ) quicksort(Array, start, mid-1 ); if ( mid + 1 < end ) quicksort(Array, mid+1, end); } } int QuickSort::partition(int Array[], int start, int end) { int i, j, x, tmp; x = Array[end]; i = start -1; for ( j = start; j < end; j++ ) { if ( Array[j] <= x) { i++; tmp = Array[j]; Array[j] = Array[i]; Array[i] = tmp; } } tmp = Array[end]; Array[end] = Array[i+1]; Array[i+1] = tmp; if (DEBUG) { printArray(Array, len, "MidResult"); } return i+1; } 測試： int a[10] = {7,3,2,9,8,5,1,10,4,6}; int len = 10; QuickSort* quicksort= new QuickSort(a, len); quicksort->sort(); printArray(a, len, "QuickSort");
