快速排序是個遞歸的過程，采取分而治之的思想。直接舉例： 有10個數：1，3，7，9，5，8，10，2，4，6；

第一步：取最后一個數 6 為節點： 第二步：將小于6的放到左邊，大于6的放到右邊，結果：1，2，5，2，4，8，10，9，7，6（6為節點） 第三步：將6和8進行交換，結果：1，2，5，2，4，6，10，9，7，8（6為節點），小于6的在左邊，大于6的在右邊，整個過程的算法的復雜度為O(n); 第四步：將節點的位置返回，6是第6個數，就返回位置5。 第五步：遞歸調用：對左邊5個數進行前4步操作，右邊4個數進行前4步操作。 前四步偽代碼《算法導論》： PARTITION(A,p,r) ? ? x=A[r] i=p-1 for j=p to r-1 if? A[j]<=x i=i+1 swap(A[i],A[j]) ? //完成前2步操作 swap(A[i+1],A[r]) ? ?? //完成第3步操作 return i+1 ? ? //返回節點的位置

遞歸的偽代碼：

QUICKSORT(A,p,r)

if?? p<r

q=PARTITION(A,p,r)?? //對數組進行初步整理

QUICKSORT(A,p,q-1)?? //遞歸節點6左邊的數

QUICKSORT(A,q+1,r)?? //遞歸節點6右邊的數
完整程序如下： 結果： 此程序最難的部分在于priotSwap這個函數,自己手動排幾個數，就能明白其中的原因了。

總結

以上是生活随笔為你收集整理的快速排序（quick sort) C++的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。