内部排序算法：快速排序

基本思想

設目前待排序的數組無序區為r[low..high]，利用分治法可将快速排序的基本思想描述為：

分解：

在r[low..high]中任選一個記錄作為基準（pivot），以此基準将目前無序區劃分為左、右兩個較小的子區間r[low..pivotpos-1)和r[pivotpos+1..high]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄（不妨記為pivot）的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正确的位置（pivotpos）上，它無需參加後續的排序。

注意：劃分的關鍵是要求出基準記錄所在的位置pivotpos，劃分的結果可以簡單地表示為（注意pivot=r[pivotpos]）：

r[low..pivotpos-1].keys ≤ r[pivotpos].key ≤ r[pivotpos+1..high].keys

其中low≤pivotpos≤high。

求解：

通過遞歸調用快速排序對左、右子區間r[low..pivotpos-1]和r[pivotpos+1..high] 快速排序。

組合：

因為當“求解”步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言， “組合”步驟不需要做什麼，可看作是空操作。

算法實作

快速排序算法，java實作，代碼如下所示：

<code>public</code> <code>abstract</code> <code>class</code> <code>sorter {</code>

<code></code><code>public</code> <code>abstract</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array);</code>

<code>public</code> <code>class</code> <code>quicksorter</code><code>extends</code> <code>sorter {</code>

<code></code><code>@override</code>

<code></code><code>public</code> <code>void</code> <code>sort(</code><code>int</code><code>[] array) {</code>

<code></code><code>quicksort(array,</code><code>0</code><code>, array.length -</code><code>1</code><code>);</code>

<code></code><code>* 通過劃分，基于分治思想，遞歸執行子任務排序最後合并</code>

<code></code><code>* @param low 數組首位置索引</code>

<code></code><code>* @param high 數組末位置索引</code>

<code></code><code>private</code> <code>void</code> <code>quicksort(</code><code>int</code><code>[] array,</code><code>int</code> <code>low,</code><code>int</code> <code>high) {</code>

<code></code><code>int</code> <code>pivotpos;</code><code>// 劃分基準元素索引</code>

<code></code><code>pivotpos = partition(array, low, high);</code>

<code></code><code>quicksort(array, low, pivotpos -</code><code>1</code><code>);</code><code>// 左劃分遞歸快速排序</code>

<code></code><code>quicksort(array, pivotpos +</code><code>1</code><code>, high);</code><code>// 右劃分遞歸快速排序</code>

<code></code><code>* 簡單劃分方法</code>

<code></code><code>* @param i</code>

<code></code><code>* @param j</code>

<code></code><code>* @return</code>

<code></code><code>private</code> <code>int</code> <code>partition(</code><code>int</code><code>[] array,</code><code>int</code> <code>i,</code><code>int</code> <code>j) {</code>

<code></code><code>integer pivot = array[i];</code><code>// 初始基準元素，如果quicksort方法第一次調用，pivot初始為數組第一個元素</code>

<code></code><code>while</code> <code>(i < j) {</code><code>// 兩個指針從兩邊向中間靠攏，不能相交</code>

<code></code><code>// 右側指針向左移動</code>

<code></code><code>while</code> <code>(j > i && array[j] >= pivot) {</code>

<code></code><code>if</code> <code>(i < j) {</code><code>// 如果在沒有使指針i和j相交的情況下找到了array[j] >= 基準元素pivot</code>

<code></code><code>array[i] = array[j];</code><code>// 基準元素放到了j指針處</code>

<code></code><code>i++;</code><code>// 左側i指針需要向右移動一個位置</code>

<code></code><code>// 左側指針向右移動</code>

<code></code><code>while</code> <code>(i < j && array[i] <= pivot) {</code>

<code></code><code>if</code> <code>(i < j) {</code><code>// 如果在沒有使指針i和j相交的情況下找到了array[i] <= 基準元素pivot</code>

<code></code><code>array[j] = array[i];</code><code>// 基準元素放到了i指針處</code>

<code></code><code>j--;</code><code>// 右側j指針需要向左移動一個位置</code>

<code></code><code>array[i] = pivot;</code><code>// 将基準元素放到正确的排序位置上</code>

<code></code><code>return</code> <code>i;</code>

快速排序算法，python實作，代碼如下所示：

<code>class</code> <code>sorter:</code>

<code></code><code>abstract sorter class, which provides shared methods being used by</code>

<code></code><code>subclasses.</code>

<code></code><code>__metaclass__</code><code>=</code> <code>abcmeta</code>

<code></code><code>@abstractmethod</code>

<code></code><code>def</code> <code>sort(</code><code>self</code><code>, array):</code>

<code>class</code> <code>quicksorter(sorter):</code>

<code></code><code>quick sorter</code>

<code></code><code>length</code><code>=</code> <code>len</code><code>(array)</code>

<code></code><code>self</code><code>.__quick_sort(array,</code><code>0</code><code>, length</code><code>-</code> <code>1</code><code>)</code>

<code></code><code>def</code> <code>__quick_sort(</code><code>self</code><code>, array, low, high):</code>

<code></code><code>pivotpos</code><code>=</code> <code>self</code><code>.__partition(array, low, high)</code>

<code></code><code>self</code><code>.__quick_sort(array, low, pivotpos</code><code>-</code> <code>1</code><code>)</code>

<code></code><code>self</code><code>.__quick_sort(array, pivotpos</code><code>+</code> <code>1</code><code>, high)</code>

<code></code><code>def</code> <code>__partition(</code><code>self</code><code>, array, i, j):</code>

<code></code><code>pivot</code><code>=</code> <code>array[i]</code>

<code></code><code>while</code> <code>i<j:</code>

<code></code><code># right side pointer moves to left</code>

<code></code><code>while</code> <code>j>i</code><code>and</code> <code>array[j]></code><code>=</code><code>pivot:</code>

<code></code><code>array[i]</code><code>=</code> <code>array[j]</code>

<code></code><code># left side pointer moves to right</code>

<code></code><code>while</code> <code>i<j</code><code>and</code> <code>array[i]<</code><code>=</code><code>pivot:</code>

<code></code><code>array[j]</code><code>=</code> <code>array[i]</code>

<code></code><code># put the pivot element to the right position</code>

<code></code><code>array[i]</code><code>=</code> <code>pivot</code>

<code></code><code>return</code> <code>i</code>

排序過程

采用分治的思想對待排序數組進行劃分。分治法的基本思想是：

将原問題分解為若幹個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然後将這些子問題的解組合為原問題的解。

快速排序，主要是求得一個合理的劃分，進而基于此劃分來分治排序。使用簡單劃分方法的思想是：

第一步：

設定兩個指針i和j，它們的初值分别為區間的下界和上界，即i=low，i=high；選取無序區的第一個記錄r[i](即r[low])作為基準記錄，并将它儲存在變量pivot中；

第二步：

首先，令j自high起向左掃描，直到找到第1個關鍵字小于pivot.key的記錄r[j]，将r[j]移至i所指的位置上，這相當于r[j]和基準r[i]（即pivot）進行了交換，使關鍵字小于基準關鍵字pivot.key的記錄移到了基準的左邊，交換後r[j]中相當于是pivot；

然後，令i指針自i+1 位置開始向右掃描，直至找到第1個關鍵字大于pivot.key的記錄r[i]，将r[i]移到i所指的位置上，這相當于交換了r[i]和基準r[j]，使關鍵字大于基準關鍵字的記錄移到了基準的右邊，交換後r[i]中又相當于存放了pivot；

接着，令指針j自位置j-1開始向左掃描，如此交替改變掃描方向，從兩端各自往中間靠攏，直至i=j時，i便是基準pivot最終的位置，将pivot放在此位置上就完成了一次劃分。

快速排序示例過程，如下所示：

假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。

首先，根據數組下界和上界，求得一個劃分，劃分過程如下：

第一次劃分：

初始化：i = 0，j=19，以第一個元素array[0] = 94為基準pivot = array[0] = 94。

首先指針j向前移動：

array[19] = 49<pivot = array[0] = 94，i = 0<j = 19，繼續移動j指針；

array[18] = 76<pivot = array[0] = 94，i = 0<j = 18，繼續移動j指針；

……

array[1] = 12<pivot = array[0] = 94，i = 0<j = 1，繼續移動j指針；

i = 0pivotpos-1 = -1排序停止；右側部分繼續遞歸執行快速排序。

第二次劃分：

對于{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}：

初始化：i = 1，j=19，以第二個元素（除了第一次劃分的基準元素）array[1] = 12為基準pivot = array[1] = 12。

array[19] = 49>=pivot = array[1] = 12成立，并且j = 19>i = 1，j指針繼續移動；

array[18] = 76>=pivot = array[1] = 12成立，并且j = 18>i = 1，j指針繼續移動；

array[17] = 65>=pivot = array[1] = 12成立，并且j = 17>i = 1，j指針繼續移動；

array[16] = 12>=pivot = array[1] = 12成立，并且j = 16>i = 1，j指針繼續移動；

array[15] = 37>=pivot = array[1] = 12成立，并且j = 15>i = 1，j指針繼續移動；

array[14] = 90>=pivot = array[1] = 12成立，并且j = 14>i = 1，j指針繼續移動；

array[13] = 83>=pivot = array[1] = 12成立，并且j = 13>i = 1，j指針繼續移動；

array[12] = 68>=pivot = array[1] = 12成立，并且j = 12>i = 1，j指針繼續移動；

array[11] = 5>=pivot = array[1] = 12不成立，j指針停止移動：

此時i = 1<j = 11，将j指針處的元素移動到i指針處：array[1] = 5（基準元素的拷貝為pivot = 12），同時i指針向後移動一次：i++，即i = 2；

子數組變為（下面左邊的12表示基準元素，實際j指針移動後并沒有移動基準元素，而是pivot變量持有它的拷貝，12 處仍然是5）：

{5,34,76,26,9,0,37,55,76,37,12,68,83,90,37,12,65,76,49}。

指針i向後移動：

array[2] = 34<=pivot = 12不成立，i指針停止移動：

此時i = 2<j = 11，将i指針處的元素移動到j指針處：array[11] = 34（基準元素的拷貝為pivot = 12），同時j指針向前移動一次：j–，即j = 10；

子數組變為：

{5,12,76,26,9,0,37,55,76,37,34,68,83,90,37,12,65,76,49}。

判斷i與j：i = 2= pivot = 12成立，并且j = 10>i = 2，j指針繼續移動；

array[9] = 76>= pivot = 12成立，并且j = 9>i = 2，j指針繼續移動；

array[8] = 55>= pivot = 12成立，并且j = 8>i = 2，j指針繼續移動；

array[7] = 37>= pivot = 12成立，并且j = 7>i = 2，j指針繼續移動；

array[6] = 0>= pivot = 12不成立，j指針停止移動：

此時j = 6>i = 2，将j指針處的元素array[6] = 0移動到i指針處：array[2] = array[6] = 0（基準元素的拷貝為pivot = 12），同時i指針向後移動一次：i++，即i = 3；

子數組變為（下面左邊的12表示基準元素，實際j指針移動後并沒有移動基準元素，而是pivot變量持有它的拷貝，12處仍然是0）：

{5,0,76,26,9,12,37,55,76,37,34,68,83,90,37,12,65,76,49}。

指針i第2次向後移動：

array[3] = 76i = 3，将i指針處的元素array[3] = 76移動到j指針處：array[6] = array[3] = 0（基準元素的拷貝為pivot = 12），同時j指針向前移動一次：j–，即j = 5；

{5,0,12,26,9,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。

判斷i與j：i = 3=pivot = 12不成立，j指針停止移動：

此時j = 5>i = 3，将j指針處的元素array[5] = 9移動到i指針處：array[3] = array[5] = 9（基準元素的拷貝為pivot = 12），同時i指針向後移動一次：i++，即i = 4；

子數組變為（下面左邊的12表示基準元素，實際j指針移動後并沒有移動基準元素，而是pivot變量持有它的拷貝，12處仍然是9）：

{5,0,9,26,12,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。

指針i第3次向後移動：

array[4] = 26i = 4，将i指針處的元素array[4] = 26移動到j指針處：array[5] = array[4] = 26（基準元素的拷貝為pivot = 12），同時j指針向前移動一次：j–，即j = 4；

{5,0,9,12,26,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。

判斷i與j：i = 4<j = 4不成立，條件不滿足：

将基準元素放到i指針處，array[4] = pivot = 12；并傳回基準元素的索引i = 4。

劃分結束。

根據得到的基準元素的索引，遞歸快速排序。

算法分析

時間複雜度

最好情況

在最好情況下，每次劃分所取的基準都是目前無序區的”中值”記錄，劃分的結果是基準的左、右兩個無序子區間的長度大緻相等，總的關鍵字比較次數：0(nlgn)。

最壞情況

最壞情況是每次劃分選取的基準都是目前無序區中關鍵字最小（或最大）的記錄，劃分的結果是基準左邊的子區間為空（或右邊的子區間為空），而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。

是以，快速排序必須做n-1次劃分，第i次劃分開始時區間長度為n-i+1，所需的比較次數為n-i(1≤i≤n-1)，故總的比較次數達到最大值：

n(n-1)/2 = o(n^2)

如果按上面給出的劃分算法，每次取目前無序區的第1個記錄為基準，那麼當檔案的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準就是目前無序區中關鍵字最小（或最大）的記錄，則快速排序所需的比較次數反而最多。

空間複雜度

快速排序在系統内部需要一個棧來實作遞歸。若每次劃分較為均勻，則其遞歸樹的高度為o(logn)，故遞歸後需棧空間為o(logn)。最壞情況下，遞歸樹的高度為o(n)，所需的棧空間為o(n)。

排序穩定性

快速排序是不穩定的。

内部排序算法：快速排序

繼續閱讀

Cloud Studio初體驗

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

在python中建立excel并寫入

hdu7108哈希