排序算法(1) 快速排序 C++實現

快速排序基本特性

1. 時間復雜度：O（n*lgn）
2. 最壞：O（n^2）
3. 空間復雜度：最好情況下：O（lgn），最壞情況：O(n)，平均情況：O(lgn)
4. 不穩定。

關於快速排序的空間復雜度，謝謝@命運他爹 同學指正。詳述一下。

快速排序由於每次遞歸的時候會占用一個空間返回中間數位置，所以一次遞歸的空間復雜度為O(1)。

最好情況和平均情況下的遞歸深度為O(lgn)，相應的空間復雜度就是O(lgn)

最壞情況下的遞歸深度為O(n)，空間復雜度為O(n)。

算法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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

一趟排序過程分析：

---

源碼

類聲明

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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; };

相關成員函數實現

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 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; }

測試：

1 2 3 4 5 6 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");

運行截圖：

------------------------------分割線------------------------------

C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm

讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm

讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm

讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm

將C語言梳理一下，分布在以下10個章節中：

1. Linux-C成長之路（一）：Linux下C編程概要 http://www.linuxidc.com/Linux/2014-05/101242.htm
2. Linux-C成長之路（二）：基本數據類型 http://www.linuxidc.com/Linux/2014-05/101242p2.htm
3. Linux-C成長之路（三）：基本IO函數操作 http://www.linuxidc.com/Linux/2014-05/101242p3.htm
4. Linux-C成長之路（四）：運算符 http://www.linuxidc.com/Linux/2014-05/101242p4.htm
5. Linux-C成長之路（五）：控制流 http://www.linuxidc.com/Linux/2014-05/101242p5.htm
6. Linux-C成長之路（六）：函數要義 http://www.linuxidc.com/Linux/2014-05/101242p6.htm
7. Linux-C成長之路（七）：數組與指針 http://www.linuxidc.com/Linux/2014-05/101242p7.htm
8. Linux-C成長之路（八）：存儲類，動態內存 http://www.linuxidc.com/Linux/2014-05/101242p8.htm
9. Linux-C成長之路（九）：復合數據類型 http://www.linuxidc.com/Linux/2014-05/101242p9.htm
10. Linux-C成長之路（十）：其他高級議題