快速排序的分治方法

㈠ 快排是什麼

快速排序

快速排序是一種高效的排序演算法，基於分治法的思想。它將待排序的數組或列表分割成若干個子序列，對每個子序列進行排序，最終合並為有序的序列。

以下是關於快速排序的詳細解釋：

1. 基本思想：快速排序的核心是分治策略。它選擇一個基準元素，將數組分為兩部分，使得比基準元素小的元素位於其左側，比基準元素大的元素位於其右側。然後，對這兩部分遞歸地進行快速排序，最終完成整個數組的排序。

2. 操作過程：在快速排序中，通常選擇數組的第一個元素作為基準值。然後，通過一趟排序將數組劃分為兩部分。在這之後，遞歸地對兩部分進行快速排序，直到劃分的部分只包含一個元素或為空為止。遞歸結束的條件是整個數組已經被完全排好序。

3. 特點：快速排序是一種不穩定的排序演算法，但在實際應用中表現良好。它的平均時間復雜度為O，其中n是待排序數組的元素個數。在最好的情況下，快速排序的性能可以接近O。但在最壞的情況下，性能可能較差。盡管如此，由於其高效性和實現的簡單性，快速排序在許多場合仍然是一種首選的排序演算法。

通過上述解釋，我們可以了解到快速排序是一種基於分治思想的排序演算法，通過將待排序序列不斷分割並遞歸地排序子序列來實現整體的排序。

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

冒泡排序為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

㈢ 快速排序演算法

快速排序是對冒泡排序演算法的一種改進，同冒泡排序一樣，快速排序也屬於交換排序，通過元素之間的比較和交換位置來達到排序的目的。

不同的是，冒泡排序在每一輪只把一個元素冒泡到數列的一端，而快速排序在每一輪挑選一個基準元素，並讓其他比它大的元素移動到數列一邊，比它小的元素移動到數列的另一邊，從而把數列拆解成了兩個部分。

快速排序是基於「分治法」原理實現，所謂分治法就是不斷地將原數組序列按照一定規律進行拆分，拆分後各自實現排序直到拆分到序列只剩下一個關鍵字為止。

快速排序首先選取一個關鍵字為標志位（關鍵字的選取影響排序效率），然後將序列中小於標志位的關鍵字移動至標志位左側，大於標志位的關鍵字移動至右側。一趟比較完成後，整個序列以選取的標志位為界，左側均小於標志位，右側均大於關鍵字。

但左右兩側內部並不是有序的（左右兩側關鍵字個數也不一定相同）。進而繼續將左右兩側分別再以這種方式進行排序，直到將序列拆分的剩餘一個關鍵字為止，整個序列即變成有序。

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

快速排序的原理：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小。

然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

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

(4)快速排序的分治方法擴展閱讀：

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

值得注意的是，快速排序不是一種穩定的排序演算法，也就是說，多個相同的值的相對位置也許會在演算法結束時產生變動。

一趟快速排序的演算法是：

1、設置兩個變數i、j，排序開始的時候：i=0，j=N-1；

2、以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3、從j開始向前搜索，即由後開始向前搜索(j--)，找到第一個小於key的值A[j]，將A[j]的值賦給A[i]；

4、從i開始向後搜索，即由前開始向後搜索(i++)，找到第一個大於key的A[i]，將A[i]的值賦給A[j]；

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指針位置不變。