使用分治法實現快速排序演算法

1. 快速排序演算法原理與實現

快速排序的基本思想就是從一個數組中任意挑選一個元素（通常來說會選擇最左邊的元素）作為中軸元素，將剩下的元素以中軸元素作為比較的標准，將小於等於中軸元素的放到中軸元素的左邊，將大於中軸元素的放到中軸元素的右邊。

然後以當前中軸元素的位置為界，將左半部分子數組和右半部分子數組看成兩個新的數組，重復上述操作，直到子數組的元素個數小於等於1（因為一個元素的數組必定是有序的）。

以下的代碼中會常常使用交換數組中兩個元素值的Swap方法，其代碼如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(1)使用分治法實現快速排序演算法擴展閱讀：

快速排序演算法 的基本思想是：將所要進行排序的數分為左右兩個部分，其中一部分的所有數據都比另外一 部分的數據小，然後將所分得的兩部分數據進行同樣的劃分，重復執行以上的劃分操作，直 到所有要進行排序的數據變為有序為止。

定義兩個變數low和high，將low、high分別設置為要進行排序的序列的起始元素和最後一個元素的下標。第一次，low和high的取值分別為0和n-1，接下來的每次取值由劃分得到的序列起始元素和最後一個元素的下標來決定。

定義一個變數key，接下來以key的取值為基準將數組A劃分為左右兩個部分，通 常，key值為要進行排序序列的第一個元素值。第一次的取值為A[0]，以後毎次取值由要劃 分序列的起始元素決定。

從high所指向的數組元素開始向左掃描，掃描的同時將下標為high的數組元素依次與劃分基準值key進行比較操作，直到high不大於low或找到第一個小於基準值key的數組元素，然後將該值賦值給low所指向的數組元素，同時將low右移一個位置。

如果low依然小於high，那麼由low所指向的數組元素開始向右掃描，掃描的同時將下標為low的數組元素值依次與劃分的基準值key進行比較操作，直到low不小於high或找到第一個大於基準值key的數組元素，然後將該值賦給high所指向的數組元素，同時將high左移一個位置。

重復步驟(3) (4)，直到low的植不小於high為止，這時成功劃分後得到的左右兩部分分別為A[low……pos-1]和A[pos+1……high]，其中，pos下標所對應的數組元素的值就是進行劃分的基準值key，所以在劃分結束時還要將下標為pos的數組元素賦值 為 key。

2. 快速排序法的平均時間復雜度和最壞時間復雜度分別是多少

快速排序的平均時間復雜度和最壞時間復雜度分別是O(nlgn)、O(n^2)。

當排序已經成為基本有序狀態時，快速排序退化為O(n^2)，一般情況下，排序為指數復雜度。

快速排序最差情況遞歸調用棧高度O(n)，平均情況遞歸調用棧高度O(logn)，而不管哪種情況棧的每一層處理時間都是O(n)，所以，平均情況（最佳情況也是平均情況）的時間復雜度O(nlogn)，最差情況的時間復雜度為O(n^2)。

(2)使用分治法實現快速排序演算法擴展閱讀

快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序，它採用了一種分治的策略，通常稱其為分治法。快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

（1）首先設定一個分界值，通過該分界值將數組分成左右兩部分。

（2）將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。

（3）然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。

（4）重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。

3. C++演算法分治法實現快速排序改錯。

你思路是錯的
快排的每一部分 是將待排序的序列中隨便挑一個 比他小的放到左邊 大的放到右邊 自己放在中間
然後遞歸解決左邊那串序列和右邊那串
怎麼可能剛好左邊那串和右邊那串長度都是原來的一半呢？

4. 分治：用循環迭代的方法實現快速排序。

#include<stdio.h>
int s1[10000];
void kuaisu1(int a,int b)
{
int i,j,t=1,m,p=0;
m=s1[a];
for(i=a,j=b;i!=j;j=j-t)
if((i-j)*(m-s1[j])<0)
{
s1[i]=s1[j];
p=i;i=j;j=p;
t=t*(-1);
}
s1[i]=m;
if(i-1-a>=1) kuaisu1(a,i-1);
if(b-i-1>=1) kuaisu1(i+1,b);
}
void main()
{
scanf("%s",s);
kuaisu1();
}

5. 作為程序員提高編程能力的幾個基礎演算法

一：快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序n個項目要Ο(nlogn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(nlogn)演算法更快，因為它的內部循環（innerloop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divideandconquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。

演算法步驟：

1從數列中挑出一個元素，稱為「基準」（pivot），

2重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。

3遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

二：堆排序演算法

堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

堆排序的平均時間復雜度為Ο(nlogn) 。

創建一個堆H[0..n-1]

把堆首（最大值）和堆尾互換

3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置

4.重復步驟2，直到堆的尺寸為1

三：歸並排序

歸並排序（Mergesort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（DivideandConquer）的一個非常典型的應用。

1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列

2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

3.比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置

4.重復步驟3直到某一指針達到序列尾

5.將另一序列剩下的所有元素直接復制到合並序列尾

四：二分查找演算法

二分查找演算法是一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半，時間復雜度為Ο(logn) 。

五：BFPRT(線性查找演算法)

BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間復雜度，五位演算法作者做了精妙的處理。

1.將n個元素每5個一組，分成n/5(上界)組。

2.取出每一組的中位數，任意排序方法，比如插入排序。

3.遞歸的調用selection演算法查找上一步中所有中位數的中位數，設為x，偶數個中位數的情況下設定為選取中間小的一個。

4.用x來分割數組，設小於等於x的個數為k，大於x的個數即為n-k。

5.若i==k，返回x；若i<k，在小於x的元素中遞歸查找第i小的元素；若i>k，在大於x的元素中遞歸查找第i-k小的元素。

終止條件：n=1時，返回的即是i小元素。

六：DFS（深度優先搜索）

深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。

深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。

深度優先遍歷圖演算法步驟：

1.訪問頂點v；

2.依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；

3.若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。

上述描述可能比較抽象，舉個實例：

DFS在訪問圖中某一起始頂點v後，由v出發，訪問它的任一鄰接頂點w1；再從w1出發，訪問與w1鄰接但還沒有訪問過的頂點w2；然後再從w2出發，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。

接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。

七：BFS(廣度優先搜索)

廣度優先搜索演算法（Breadth-First-Search），是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。

BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。

1.首先將根節點放入隊列中。

2.從隊列中取出第一個節點，並檢驗它是否為目標。

如果找到目標，則結束搜尋並回傳結果。

否則將它所有尚未檢驗過的直接子節點加入隊列中。

3.若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。

4.重復步驟2。

八：Dijkstra演算法

戴克斯特拉演算法（Dijkstra』salgorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

該演算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u,v)表示從頂點u到v有路徑相連。我們以E表示G中所有邊的集合，而邊的權重則由權重函數w:E→[0,∞]定義。因此，w(u,v)就是從頂點u到頂點v的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有V中有頂點s及t，Dijkstra演算法可以找到s到t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點s到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。

1.初始時令S=,T=，T中頂點對應的距離值

若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值

若不存在<V0,Vi>，d(V0,Vi)為∞

2.從T中選取一個其距離值為最小的頂點W且不在S中，加入S

3.對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

九：動態規劃演算法

動態規劃（Dynamicprogramming）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。

關於動態規劃最經典的問題當屬背包問題。

1.最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動態規劃演算法解決問題提供了重要線索。

2.子問題重疊性質。子問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重復計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地查看一下結果，從而獲得較高的效率。

十：樸素貝葉斯分類演算法

樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單概率分類演算法。貝葉斯分類的基礎是概率推理，就是在各種條件的存在不確定，僅知其出現概率的情況下，如何完成推理和決策任務。概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。

樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換言樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。

盡管是帶著這些樸素思想和過於簡單化的假設，但樸素貝葉斯分類器在很多復雜的現實情形中仍能夠取得相當好的效果。

通過掌握以上演算法，能夠幫你迅速提高編程能力，成為一名優秀的程序員。

6. 按鍵精靈快速排序（比冒泡更快更有效率的演算法）是怎麼樣的

冒泡排序為O(N^2)，在排序過程中其實是效率較低的。在掃拍賣或者其他需要比拼速度的時候，時間就是金錢~越快越能搶佔先機。
今天我們介紹另一種更快更有效率的排序——快速排序，時間復雜度為O(n*logn)。

快速排序的演算法思想
快速排序採用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。
該方法的基本思想是：
1．先從數列中取出一個數作為基準數。（不要被這個名詞嚇到了，就是一個用來參照的數，待會你就知道它用來做啥的了）。
2．分區過程，將比這個數大的數全放到它的右邊，小於或等於它的數全放到它的左邊。
3 . 再對左右區間重復第二步，直到各區間只有一個數。

白話講解演算法：

假設我們現在對「6 1 2 7 9 3 4 5 10 8」這個10個數進行排序。就讓第一個數6作為基準數吧。接下來，需要將這個序列中所有比基準數大的數放在6的右邊，比基準數小的數放在6的左邊。
方法其實很簡單：分別從初始序列「6 1 2 7 9 3 4 5 10 8」兩端開始「探測」。先從右往左找一個小於6的數，再從左往右找一個大於6的數，然後交換他們。這里可以用兩個變數i和j，分別指向序列最左邊和最右邊。我們為這兩個變數起個好聽的名字「哨兵i」和「哨兵j」。剛開始的時候讓哨兵i指向序列的最左邊（即i=1），指向數字6。讓哨兵j指向序列的最右邊（即=10），指向數字。

2014-8-29 13:45 上傳
下載附件 (9.51 KB)

首先哨兵j開始出動。因為此處設置的基準數是最左邊的數，所以需要讓哨兵j先出動，這一點非常重要（請自己想一想為什麼）。哨兵j一步一步地向左挪動（即j--），直到找到一個小於6的數停下來。接下來哨兵i再一步一步向右挪動（即i++），直到找到一個數大於6的數停下來。最後哨兵j停在了數字5面前，哨兵i停在了數字7面前。

2014-8-29 13:45 上傳
下載附件 (9.74 KB)

2014-8-29 13:45 上傳
下載附件 (8.13 KB)

現在交換哨兵i和哨兵j所指向的元素的值。交換之後的序列如下：
6 1 2 5 9 3 4 7 10 8

2014-8-29 13:45 上傳
下載附件 (9.74 KB)

2014-8-29 13:45 上傳
下載附件 (8.37 KB)

到此，第一次交換結束。接下來開始哨兵j繼續向左挪動（再友情提醒，每次必須是哨兵j先出發）。他發現了4（比基準數6要小，滿足要求）之後停了下來。哨兵i也繼續向右挪動的，他發現了9（比基準數6要大，滿足要求）之後停了下來。此時再次進行交換，交換之後的序列如下：
6 1 2 5 4 3 9 7 10 8

第二次交換結束，「探測」繼續。哨兵j繼續向左挪動，他發現了3（比基準數6要小，滿足要求）之後又停了下來。哨兵i繼續向右移動，糟啦！此時哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。說明此時「探測」結束。我們將基準數6和3進行交換。交換之後的序列如下：
3 1 2 5 4 6 9 7 10 8

2014-8-29 13:45 上傳
下載附件 (8.28 KB)

2014-8-29 13:45 上傳
下載附件 (10.45 KB)

2014-8-29 13:45 上傳
下載附件 (8.48 KB)

到此第一輪「探測」真正結束。此時以基準數6為分界點，6左邊的數都小於等於6，6右邊的數都大於等於6。回顧一下剛才的過程，其實哨兵j的使命就是要找小於基準數的數，而哨兵i的使命就是要找大於基準數的數，直到i和j碰頭為止。

OK，解釋完畢。現在基準數6已經歸位，它正好處在序列的第6位。

3

1

2

5

4

6

9

7

10

8

此時我們已經將原來的序列，以6為分界點拆分成了兩個序列，左邊的序列是「3 1 2 5 4」，右邊的序列是「9 7 10 8」。接下來還需要分別處理這兩個序列。因為6左邊和右邊的序列目前都還是很混亂的。不過不要緊，我們已經掌握了方法，接下來只要模擬剛才的方法分別處理6左邊和右邊的序列即可。現在先來處理6左邊的序列現吧。
左邊的序列是「3 1 2 5 4」。請將這個序列以3為基準數進行調整，使得3左邊的數都小於等於3，3右邊的數都大於等於3。

3

1

2

5

4

第一次交換完：以3為分界點，拆分了兩個序列。左邊都比3小，右邊都比3大。

2

1

3

5

4

再分別處理3左右的兩個序列「2 1」和「5 4」

1

2

3

4

5

這樣，最初我們劃分的6左側的序列都已經處理好了~~我們再來處理6右側的序列

9

7

10

8

以9為基準數，第一次交換完：

9

7

8

10

第二次交換：

8

7

9

10

再交換一次：

7

8

9

10

這樣，我們整個序列就排序完畢了

1

2

3

4

5

6

7

8

9

10

快排演算法代碼實現：

su = "6|1|2|7|9|3|4|5|10|8"
su=Split(su, "|")
L = UBound(su)
Call ks(0, L)
Function ks(L, B)
If L > B Then
Exit Function
End If //判斷數組上標下標是否超出范圍
i = L
j = B
key =int( su(L) ) //數組第一位提取作為基數
While j>i
While int ( su(j)) >= key and j > i //要先從最右邊開始找 找到第一個小於key的數 這里添加的j>i的判斷是為了防止j的值不斷遞減導致下標越界
j = j - 1
Wend
While int (su(i)) <= key and j > i //從最左邊開始找 找到第一個大於key的數 （這里的字元串數組需要轉換為數值型）
i = i + 1
Wend
If j>i then // 將和基數key對比得到的兩個數對換 將大於key的值往右邊放 小於key的值往左邊放
T = su(i)
su(i) = su(j)
su(j) = T
End If
Wend // 這個 While 循環當i=j 第一輪比較完退出
su(L) = su(i) // 重新設置數組第一個元素為基數
su(i) = key// 基數歸位 （排完一輪之後 左邊的數<基數<右邊的數 那麼基數就到了排序中它該在的位置。）
Call ks(L, i - 1)//繼續處理左邊的數
Call ks(i + 1, B)//繼續處理右邊的數
End Function
For i = 0 To UBound(su)
TracePrint su(i)
Next

7. 用分治法實現一組無序序列的兩路合並排序和快速排序。要求清楚合並排序及快速排序 的基本原理，編程實現分

合並排序就是將待排數列分成若干組，每組兩個數，排序；再一層一層地合並 並 排序，回到最後一層就ok了；
快排就是先確立中間點，在兩邊不停地比較，保證在中點左邊的數比中點數小，右邊的大（從大往小排則相反），遇到不符合的就左右交換，直至中點數確定；再排序中點數前面一條數列和後面一條數列，直到全部有序。
程序自己思考（下載個Free Pascal，到FPC這個文件夾里搜'qsort.pp'就有快排程序！）

8. 快速排序特點

快速排序（Quicksort）是對冒泡排序的一種改進，由東尼·霍爾在1960年提出。 快速排序是指通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序。整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

分類
排序演算法

數據結構
不定

最壞空間復雜度
根據實現的方式不同而不同
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。

步驟為：

從數列中挑出一個元素，稱為「基準」（pivot），

重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任何一邊）。在這個分區結束之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。

遞歸地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個演算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

在簡單的偽代碼中，此演算法可以被表示為：

function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if x<pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}
原地（in-place）分區的版本

上面簡單版本的缺點是，它需要的額外存儲空間，也就跟歸並排序一樣不好。額外需要的存儲器空間配置，在實際上的實現，也會極度影響速度和緩存的性能。有一個比較復雜使用原地（in-place）分區演算法的版本，且在好的基準選擇上，平均可以達到空間的使用復雜度。

function partition(a, left, right, pivotIndex)
{
pivotValue = a[pivotIndex]
swap(a[pivotIndex], a[right]) // 把pivot移到結尾
storeIndex = left
for i from left to right-1
{
if a[i]<= pivotValue
{
swap(a[storeIndex], a[i])
storeIndex = storeIndex + 1
}
}
swap(a[right], a[storeIndex]) // 把pivot移到它最後的地方
return storeIndex
}
這是原地分區演算法，它分區了標示為"左邊（left）"和"右邊（right）"的序列部分，藉由移動小於的所有元素到子序列的開頭，留下所有大於或等於的元素接在他們後面。在這個過程它也為基準元素找尋最後擺放的位置，也就是它回傳的值。它暫時地把基準元素移到子序列的結尾，而不會被前述方式影響到。由於演算法只使用交換，因此最後的數列與原先的數列擁有一樣的元素。要注意的是，一個元素在到達它的最後位置前，可能會被交換很多次。

一旦我們有了這個分區演算法，要寫快速排列本身就很容易：

procere quicksort(a, left, right)
if right>left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
這個版本經常會被使用在命令式語言中，像是C語言。

快速排序
快速排序是二叉查找樹（二叉搜索樹）的一個空間最優化版本。不是循序地把數據項插入到一個明確的樹中，而是由快速排序組織這些數據項到一個由遞歸調用所隱含的樹中。這兩個演算法完全地產生相同的比較次數，但是順序不同。對於排序演算法的穩定性指標，原地分區版本的快速排序演算法是不穩定的。其他變種是可以通過犧牲性能和空間來維護穩定性的。

9. 快速排序原理是什麼

先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束。
在當前無序區R[1..H]中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：R[1..I-1]和R[I+1..H]，且左邊的無序子區中數據元素均小於等於基準元素，右邊的無序子區中數據元素均大於等於基準元素，而基準X則位於最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止
快速排序的基本思想是基於分治策略的。對於輸入的子序列L[p..r]，如果規模足夠小則直接進行排序（比如用前述的冒泡、選擇、插入排序均可），否則分三步處理：
分解(Divide)：將待排序列L[p..r]劃分為兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大於L[q+1..r]中任一元素的值。具體可通過這樣的途徑實現：在序列L[p..r]中選擇數據元素L[q]，經比較和移動後，L[q]將處於L[p..r]中間的適當位置，使得數據元素L[q]的值小於L[q+1..r]中任一元素的值。
遞歸求解(Conquer)：通過遞歸調用快速排序演算法，分別對L[p..q]和L[q+1..r]進行排序。
合並(Merge)：由於對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序後不需要執行任何計算L[p..r]就已排好序，即自然合並。
這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典應用實例之一。

10. 快速排序演算法（free pascal)詳解，不要源程序，時間復雜度n（logn）；謝了//

快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：

1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；

2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；

3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；

4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；

5）、重復第3、4步，直到I>j；

詳細過程舉例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61

快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var a:array[0..10] of integer；
n:integer;
procere qsort(l,r:longint);{r，l表示集合的左右邊界，即把第r到第l個數進行排序}
var i,j,m:longint;
begin
m:=a[l];{標准數}
i:=l; {I，J為指針}
j:=r;
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j); {如果集合中不止一個數則進入下一層遞歸，l，J為新邊界}
if i<rthen qsort(i,r); {如果集合中不止一個數則進入下一層遞歸，i，r為新邊界}
end;
begin
for n:=1 to 10 do read(a[n]);
qsort(1,10);
for n:=1 to 10 do write(a[n]:4);
end.