快速排序演算法分享

❶ 快速排序演算法

第一趟排序後數組中的元素排列為37、35、38、36、47、53、65、73；
第二趟排序後數組中的元素排列為36、35、37、38、47、53、65、73；
第三趟排序後數組中的元素排列為35、36、37、38、47、53、65、73；
第四趟排序後數組中的元素排列為35、36、37、38、47、53、65、73；
第五趟排序後數組中的元素排列為35、36、37、38、47、53、65、73；
第六趟排序後數組中的元素排列為35、36、37、38、47、53、65、73；
第七趟排序後數組中的元素排列為35、36、37、38、47、53、65、73；
第八趟排序後數組中的元素排列為35、36、37、38、47、53、65、73。

❷ C語言的快速排序的演算法是什麼啊

快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 演算法過程設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它小的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。 一趟快速排序的演算法是： 1）設置兩個變數I、J，排序開始的時候：I=0，J=N-1； 2）以第一個數組元素作為關鍵數據，賦值給key，即 key=A[0]； 3）從J開始向前搜索，即由後開始向前搜索（J=J-1），找到第一個小於key的值A[J]，並與key交換； 4）從I開始向後搜索，即由前開始向後搜索（I=I+1），找到第一個大於key的A[I]，與key交換； 5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。找到並交換的時候i， j指針位置不變。另外當i=j這過程一定正好是i+或j-完成的最後另循環結束。) 例如：待排序的數組A的值分別是：（初始關鍵數據：X=49） 注意關鍵X永遠不變，永遠是和X進行比較，無論在什麼位子，最後的目的就是把X放在中間，小的放前面大的放後面。 A[0] A[1] A[2] A[3] A[4] A[5] A[6]： 49 38 65 97 76 13 27 進行第一次交換後：27 38 65 97 76 13 49 ( 按照演算法的第三步從後面開始找) 進行第二次交換後：27 38 49 97 76 13 65 ( 按照演算法的第四步從前面開始找>X的值，65>49,兩者交換，此時：I=3 ) 進行第三次交換後：27 38 13 97 76 49 65 ( 按照演算法的第五步將又一次執行演算法的第三步從後開始找 進行第四次交換後：27 38 13 49 76 97 65 ( 按照演算法的第四步從前面開始找大於X的值，97>49,兩者交換，此時：I=4,J=6 ) 此時再執行第三步的時候就發現I=J，從而結束一趟快速排序，那麼經過一趟快速排序之後的結果是：27 38 13 49 76 97 65，即所有大於49的數全部在49的後面，所有小於49的數全部在49的前面。 快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示： 初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序 {27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。 {76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。

❸ 常見的幾種排序演算法總結

對於非科班生的我來說，演算法似乎對我來說是個難點，查閱了一些資料，趁此來了解一下幾種排序演算法。
首先了解一下，什麼是程序

關於排序演算法通常我們所說的往往指的是內部排序演算法，即數據記錄在內存中進行排序。
排序演算法大體可分為兩種：
一種是比較排序，時間復雜度O(nlogn) ~ O(n^2)，主要有：冒泡排序，選擇排序，插入排序，歸並排序，堆排序，快速排序等。
另一種是非比較排序，時間復雜度可以達到O(n)，主要有：計數排序，基數排序，桶排序等

冒泡排序它重復地走訪過要排序的元素，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們調換過來，直到沒有元素再需要交換，排序完成。這個演算法的名字由來是因為越小(或越大)的元素會經由交換慢慢「浮」到數列的頂端。

選擇排序類似於冒泡排序，只不過選擇排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然後再從剩餘未排序元素中繼續尋找最小（大）元素，放到已排序序列的末尾，以此類推，直到所有元素均排序完畢。

插入排序比冒泡排序和選擇排序更有效率，插入排序類似於生活中抓撲克牌來。
插入排序具體演算法描述，以數組[3, 2, 4, 5, 1]為例。

前面三種排序演算法只有教學價值，因為效率低，很少實際使用。歸並排序（Merge sort）則是一種被廣泛使用的排序方法。
它的基本思想是，將兩個已經排序的數組合並，要比從頭開始排序所有元素來得快。因此，可以將數組拆開，分成n個只有一個元素的數組，然後不斷地兩兩合並，直到全部排序完成。
以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下：

有了merge函數，就可以對任意數組排序了。基本方法是將數組不斷地拆成兩半，直到每一半隻包含零個元素或一個元素為止，然後就用merge函數，將拆成兩半的數組不斷合並，直到合並成一整個排序完成的數組。

快速排序（quick sort）是公認最快的排序演算法之一，有著廣泛的應用。
快速排序演算法步驟

參考：
常用排序演算法總結(一)
阮一峰-演算法總結

❹ 快速排序法

快速排序（Quicksort）是對冒泡排序的一種改進。[1]

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。[1]

中文名
快速排序演算法
外文名
quick sort
別名
快速排序
提出者
C. A. R. Hoare
提出時間
1960年
快速
導航
排序步驟

程序調用舉例

示例代碼

性能分析
排序流程
快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：[2]
(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。[2]
(2)將大於或等於分界值的數據集中到數組右邊，小於分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小於或等於分界值，而右邊部分中各元素都大於或等於分界值。[2]
(3)然後，左邊和右邊的數據可以獨立排序。對於左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。[2]
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成後，整個數組的排序也就完成了。[2]
排序步驟
原理
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選

快排圖
用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。[1]
一趟快速排序的演算法是：[1]
1）設置兩個變數i、j，排序開始的時候：i=0，j=N-1；[1]
2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；[1]
3）從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]的值交換；[1]
4）從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]和A[j]的值交換；[1]
5）重復第3、4步，直到i==j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。[1]
排序演示
假設一開始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。
此時，ref=5，i=1，j=11，從後往前找，第一個比5小的數是x8=2，因此序列為：2，3，7，6，4，1，0，5，9，10，8。
此時i=1，j=8，從前往後找，第一個比5大的數是x3=7，因此序列為：2，3，5，6，4，1，0，7，9，10，8。
此時，i=3，j=8，從第8位往前找，第一個比5小的數是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

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

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

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

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

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

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(5)快速排序演算法分享擴展閱讀：

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

定義兩個變數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。

❻ 快速排序演算法

快速排序（Quicksort）是對冒泡排序的一種改進。

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

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

快速排序演算法通過多次比較和交換來實現排序，其排序流程如下：

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

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

❼ 快速排序法 pascal

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

假設要排序的數組是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.