排序算法(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成長之路（十）：其他高級議題