快速排序基本特性

時(shí)間復(fù)雜度：O（n*lgn）

最壞：O（n^2）

空間復(fù)雜度：最好情況下：O（lgn），最壞情況：O(n)，平均情況：O(lgn)

不穩(wěn)定。

關(guān)于快速排序的空間復(fù)雜度，謝謝@命運(yùn)他爹 同學(xué)指正。詳述一下。

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

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

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

算法

QUICKSORT(A, p, r) ? ??if?p < r ? ? ? ?then q ← PARTITION(A, p, r)??//關(guān)鍵 ? ? ? ? ? ??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

示例

?

待排序數(shù)組：7? 3? 5? 9? 8? 5? 1? 10? 4? 6

源碼類聲明 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; }; ////相關(guān)成員函數(shù)實(shí)現(xiàn)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 main(int argc, char* argv[]) {//printf("Hello World!\n");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:");system("pause");//用于暫停return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/rinack/p/4294162.html

總結(jié)

以上是生活随笔為你收集整理的排序算法(1) 快速排序 C++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。