簡介

快速排序是一種高效的比較排序算法，由 C. A. R. Hoare 于 1960 年發(fā)明。它以其平均時間復雜度 O(n log n) 和空間復雜度 O(log n) 而聞名，使其非常適合對大型數(shù)據(jù)集進行排序。

概念

快速排序基于分治策略，將問題分解為較小的問題。它通過以下步驟工作：1. 選擇基準：從數(shù)組中選擇一個元素作為基準。2. 分區(qū)：將數(shù)組分成兩部分：一部分包含所有比基準小的元素，另一部分包含所有比基準大的元素。3. 遞歸：分別對兩個分區(qū)遞歸地應用快速排序。

高效實現(xiàn)

要有效地實現(xiàn)快速排序，需要考慮以下優(yōu)化：選擇基準選擇一個好的基準至關重要，因為這會影響排序的效率。以下是一些常見的基準選擇策略：隨機基準：從數(shù)組中隨機選擇一個元素作為基準。這可以防止最壞情況出現(xiàn)。三路快速排序：將數(shù)組分成三部分：小于、等于和大于基準的元素。這可以更有效地處理重復元素。優(yōu)化分區(qū)分區(qū)算法可以優(yōu)化以減少比較和交換次數(shù)。以下是一些優(yōu)化技術(shù)：荷蘭國旗分區(qū)：使用三個指針來遍歷數(shù)組，分別表示小于、等于和大于基準的元素。這可以更快地進行分區(qū)。中位數(shù)選取：在進行分區(qū)之前，找到數(shù)組中三個中位數(shù)并選擇中位數(shù)作為基準。這可以為大多數(shù)輸入提供更好的性能。尾遞歸優(yōu)化在對分區(qū)遞歸調(diào)用快速排序時，可以使用尾遞歸優(yōu)化來消除不必要的函數(shù)調(diào)用。這可以提高性能，尤其是在數(shù)組較大的情況下。

示例代碼

以下是用 Java 實現(xiàn)的快速排序示例代碼：```javapublic class QuickSort {public static void sort(int[] arr) {sort(arr, 0, arr.length - 1);}private static void sort(int[] arr, int low, int high) {if (low < high) {int partitionIndex = partition(arr, low, high);sort(arr, low, partitionIndex - 1);sort(arr, partitionIndex + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;}}```

性能分析

快速排序的平均時間復雜度為 O(n log n)，空間復雜度為 O(log n)。最壞情況下的時間復雜度為 O(n2)，當數(shù)組已排序或逆序時會出現(xiàn)這種情況。

應用

快速排序因其效率而廣泛用于各種應用，包括：排序大數(shù)據(jù)集文件系統(tǒng)中的文件排序數(shù)據(jù)庫中的記錄排序計算機圖形學中的幾何形狀排序

結(jié)論

快速排序是一種高效且廣泛使用的排序算法，用于處理大型數(shù)據(jù)集。通過選擇一個好的基準、優(yōu)化分區(qū)算法和使用尾遞歸優(yōu)化，可以顯著提高其性能。通過了解快速排序的概念和實現(xiàn)細節(jié)，開發(fā)者可以最大化其排序任務的效率。

---

快速排序是如何通過一趟排序?qū)崿F(xiàn)數(shù)組分割的？

快速排序的遞歸奧秘

快速排序是一種高效的排序算法，其核心思想是通過一趟排序?qū)?shù)組分割成兩部分，一部分所有數(shù)據(jù)小于另一部分，然后遞歸地對這兩部分進行排序。 理解這個過程的關鍵在于遞歸調(diào)用自身。

首先，我們從一個待排序的數(shù)組 A[1]...A[N] 出發(fā)。 選擇一個基準元素，通常選擇第一個元素作為起點，將其稱為 X。 接著，設立兩個指針 I 和 J，分別指向數(shù)組的起始和結(jié)束。

一趟快速排序 如此進行：從 J 開始向前搜索，遇到小于 X 的元素就將其與 I 位置的元素交換；同時，從 I 向后搜索，找到大于 X 的元素進行交換。 這個過程會一直持續(xù)，直到 I 和 J 指針相遇。

值得注意的是，快速排序的 遞歸特性：當劃分完成后，對左右兩部分再次執(zhí)行相同的排序步驟，直到每個子數(shù)組只剩下一個元素或為空，遞歸結(jié)束。 這是一種典型的分治策略，每一次遞歸都將問題規(guī)模縮小，直至達到基本情況。

然而，快速排序并非 穩(wěn)定排序，相同元素的相對位置可能會在排序過程中改變。 這源于交換操作，可能會打亂相同值的順序。

在代碼實現(xiàn)中，遞歸調(diào)用的偽代碼如下：

總的來說，快速排序的遞歸過程如同一場精密的舞者編排，每個元素都在有序與無序之間優(yōu)雅地切換，直至整個序列井然有序。 希望這篇文章能幫助你深入了解快速排序的遞歸之美。

C語言實現(xiàn)文件排序

常見排序算法（冒泡，選擇，快速）的C語言實現(xiàn)要實現(xiàn)這幾種算法的關鍵是要熟悉算法的思想。 簡單的說，冒泡排序，就如名字說的，每經(jīng)過一輪排序，將最大的數(shù)沉到最底部。 選擇排序的思想是將整個數(shù)列，分為有序區(qū)和無序區(qū)。 每輪排序，將無序區(qū)里的最小數(shù)移入到有序區(qū)。 快速排序的思想是以一個數(shù)為中心，通常這個數(shù)是該數(shù)列第一個數(shù)，將整個數(shù)列分為兩個部分，一個部分是大于這個數(shù)的區(qū)域，一個部分是小于這個數(shù)的區(qū)域。 然后再對這兩個部分的數(shù)列分別排序。 如果將數(shù)列分為兩個部分是通過，一方面從后向前的搜索，另一方面從前向后的搜索來實現(xiàn)的。 具體的參考后面的來自網(wǎng)絡百科的文檔。 從這幾個簡單的排序算法上看，有幾個特點：冒泡排序是最簡單的，也是最穩(wěn)定的算法。 選擇排序不太穩(wěn)定，但是效率上較冒泡還是有較大的提升。 其實在分析的過程中就能發(fā)現(xiàn)，選擇排序和冒泡排序相比，中間少了很多的交換過程，和比較的次數(shù)，這個應該是時間較少的原因。 選擇排序能夠滿足一般的使用。 當比較的數(shù)超過以萬為單位時，選擇排序也還是要一點時間的。 快速排序據(jù)說是最快的。 這個可以從思想上看的出來。 ，當記錄較多的時候，快速排序的比較循環(huán)次數(shù)比上面2個都要少。 但是在具體的實現(xiàn)過程中，并不見得如此。 這是因為遞歸效率的低下導致的。 當然，估計在實際使用過的過程，快速排序估計都會使用非遞歸操作棧的方式來實現(xiàn)。 那樣應該會效率高傷不少。 估計我會在后期出一個快速排序的非遞歸實現(xiàn)來真正比較它們3個性能。 在下面的程序中，可以通過調(diào)高N的數(shù)字就能看的出來冒泡排序和選擇排序性能的差異。 在N較小，大概幾百的時候，是看不出來的。 N較大的的時候，比如N=1000或者N=的時候，快速排序的遞歸實現(xiàn)就會卡死在那里了，出不了結(jié)果。 以下是具體的代碼：/*** 常見排序算法比較 */#include #include #include #include #define N 10#define Demo 1void BubbleSort(int arr[], int n);void SelectSort(int arr[], int n);void QuickSort(int arr[], int n);void PrintArray(int arr[], int n);void GenerateArray(int arr[], int n);int main(int argc, char *argv[]){int arr[N];GenerateArray(arr, N); #if Demoprintf(Before the bubble sort------------------------\n);PrintArray(arr, N);#endifprintf(Start Bubble sort----------------------\n);clock_t start_time1=clock(); //開始計時 BubbleSort(arr, N);clock_t end_time1=clock(); // 結(jié)束計時 printf(Running time is: %lf ms\n, (double)(end_time1-start_time1)/CLOCKS_PER_SEC*1000); //輸出運行時間#if Demoprintf(After the bubble sort------------------------\n);PrintArray(arr, N);#endifprintf(-----------------------------------------------------------\n);sleep(1000); // 單位是毫秒即千分之一秒 GenerateArray(arr, N); #if Demoprintf(Before the selection sort------------------------\n);PrintArray(arr, N);#endifprintf(Start selection sort----------------------\n);clock_t start_time2=clock(); //開始計時 SelectSort(arr, N);clock_t end_time2=clock(); // 結(jié)束計時 printf(Running time is: %lf ms\n, (double)(end_time2-start_time2)/CLOCKS_PER_SEC*1000); //輸出運行時間#if Demoprintf(After the selection sort------------------------\n);PrintArray(arr, N);#endifprintf(-----------------------------------------------------------\n);sleep(1000); // 單位是毫秒即千分之一秒 GenerateArray(arr, N); #if Demoprintf(Before the quick sort------------------------\n);PrintArray(arr, N);#endifprintf(Start quick sort----------------------\n);clock_t start_time3=clock(); //開始計時 QuickSort(arr, N);clock_t end_time3=clock(); // 結(jié)束計時 printf(Running time is: %lf ms\n, (double)(end_time3-start_time3)/CLOCKS_PER_SEC*1000); //輸出運行時間#if Demoprintf(After the quick sort------------------------\n);PrintArray(arr, N);#endifsystem(PAUSE); return 0;}// 產(chǎn)生隨機列表 void GenerateArray(int arr[], int n){ int i; srand((unsigned)time(0)); for(i = 0; i arr[j + 1]) { arr[j] = arr[j] ^ arr[j+1]; arr[j+1] = arr[j] ^ arr[j+1]; arr[j] = arr[j] ^ arr[j+1]; } } }// 快速排序的遞歸實現(xiàn) void QuickSort(int arr[], int n){ if(n <= 1) return; int i =0 , j = n - 1; int key = arr[0]; int index = 0; while(i < j) { // 從后向前搜索 while(j > i && arr[j] > key) j--; if(j == i) break; else { //交換 a[j] a[i] arr[j] = arr[j] ^arr[i]; arr[i] = arr[j] ^arr[i]; arr[j] = arr[j] ^arr[i]; index = j; } // 從前向后搜索 while(i < j && arr[i] 三， 關于隨機數(shù)生成的2個函數(shù) srand()種子發(fā)生器函數(shù)，還有rand()隨機數(shù)生成器函數(shù)，自己可以參考相關文檔。 四， Demo宏來控制是演示還是比較性能用的。 當把N調(diào)整的很小，比如10的時候，可以設置Demo為1，那樣就能打印數(shù)組了，可以看到比較前后的情況。 當把N調(diào)整到很大比如的時候，就把Demo設置為0，那樣就不打印數(shù)組，直接比較性能。 具體的算法文檔參考下面的：冒泡排序基本概念冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。 即在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。 然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。 至此第一趟結(jié)束，將最大的數(shù)放到了最后。 在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。 如此下去，重復以上過程，直至最終完成排序。 由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當于氣泡往上升，所以稱作冒泡排序。 用二重循環(huán)實現(xiàn)，外循環(huán)變量設為i，內(nèi)循環(huán)變量設為j。 外循環(huán)重復9次，內(nèi)循環(huán)依次重復9，8，...，1次。 每次進行比較的兩個元素都是與內(nèi)循環(huán)j有關的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,9，對于每一個i, j的值依次為1,2,...10-i。 產(chǎn)生在許多程序設計中，我們需要將一個數(shù)列進行排序，以方便統(tǒng)計，而冒泡排序一直由于其簡潔的思想方法而倍受青睞。 排序過程設想被排序的數(shù)組R［1..N］垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上漂浮，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。 算法示例A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：49 38 65 97 76 13 27第一趟冒泡排序過程38 49 65 97 76 13 2738 49 65 97 76 13 2738 49 65 97 76 13 2738 49 65 76 97 13 2738 49 65 76 13 97 2738 49 65 76 13 27 97 – 這是第一趟冒泡排序完的結(jié)果第二趟也是重復上面的過程，只不過不需要比較最后那個數(shù)97，因為它已經(jīng)是最大的38 49 65 13 27 76 97 – 這是結(jié)果第三趟繼續(xù)重復，但是不需要比較倒數(shù)2個數(shù)了38 49 13 27 65 76 97….選擇排序基本思想n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果：①初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空。 ②第1趟排序在無序區(qū)R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區(qū)的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。 ……③第i趟排序第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。 該趟排序從當前無序區(qū)中選出關鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，使R[1..i]和R分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。 這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果。 常見的選擇排序細分為簡單選擇排序、樹形選擇排序（錦標賽排序）、堆排序。 上述算法僅是簡單選擇排序的步驟。 排序過程A[0] 、 A[1]、 A[2]、 A[3]、 A[4]、 A[5]、 A[6]：49 38 65 97 76 13 27第一趟排序后 13 ［38 65 97 76 49 27]第二趟排序后 13 27 ［65 97 76 49 38]第三趟排序后 13 27 38 [97 76 49 65]第四趟排序后 13 27 38 49 [76 97 65]第五趟排序后 13 27 38 49 65 [97 76]第六趟排序后 13 27 38 49 65 76 [97]最后排序結(jié)果 13 27 38 49 49 65 76 97快速排序算法算法過程設要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。 一趟快速排序的算法是：1）設置兩個變量I、J，排序開始的時候：I=0，J=N-1；2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給key，即 key=A[0]；3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個小于key的值A[J]，并與A[I]交換；4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個大于key的A[I]，與A[J]交換；5）重復第3、4、5步，直到 I=J； (3,4步是在程序中沒找到時候j=j-1，i=i+1，直至找到為止。 找到并交換的時候i， j指針位置不變。 另外當i=j這過程一定正好是i+或j+完成的最后另循環(huán)結(jié)束)例如：待排序的數(shù)組A的值分別是：（初始關鍵數(shù)據(jù)：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( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找進行第四次交換后： 27 38 13 49 76 97 65( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時：I=4,J=6 )此時再執(zhí)行第三步的時候就發(fā)現(xiàn)I=J，從而結(jié)束一趟快速排序，那么經(jīng)過一趟快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。 快速排序就是遞歸調(diào)用此過程——在以49為中點分割這個數(shù)據(jù)序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個有序的序列，根據(jù)這種思想對于上述數(shù)組A的快速排序的全過程如圖6所示：初始狀態(tài) {49 38 65 97 76 13 27}進行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}分別對前后兩部分進行快速排序 {27 38 13} 經(jīng)第三步和第四步交換后變成 {13 27 38} 完成排序。 {76 97 65} 經(jīng)第三步和第四步交換后變成 {65 76 97} 完成排序。

如何用java實現(xiàn)快速排序，簡答講解下原理

快速排序思想：通過對數(shù)據(jù)元素集合Rn 進行一趟排序劃分出獨立的兩個部分。 其中一個部分的關鍵字比另一部分的關鍵字小。 然后再分別對兩個部分的關鍵字進行一趟排序，直到獨立的元素只有一個，此時整個元素集合有序。 快速排序的過程，對一個元素集合R[ low ... high ] ,首先取一個數(shù)（一般是R[low] ）做參照 ， 以R[low]為基準重新排列所有的元素。 所有比R[low]小的放前面，所有比R[low] 大的放后面，然后以R[low]為分界，對R[low ... high] 劃分為兩個子集和，再做劃分。 直到low >=high 。 比如：對R={37, 40, 38, 42, 461, 5, 7, 9, 12}進行一趟快速排序的過程如下(注:下面描述的內(nèi)容中元素下表從 0 開始)：開始選取基準 base = 37，初始位置下表 low = 0 ， high = 8， 從high=8，開始如果R[8] < base ,將high位置中的內(nèi)容寫入到R[low]中, 將high位置空出來, low = low +1 ;從low開始探測，由于low=1 ， R[low] > base ,所以將R[low]寫入到R[high] , high = high -1 ;檢測到low < high ,所以第一趟快速排序仍需繼續(xù):此時low=1，high=7，因為 R[high] < base ,所以將 R[high] 寫入到到R[low]中,low = low + 1;從low開始探測,low = 2 , R[low] >base ,所以講R[low]寫入到R[high]，high=high-1;繼續(xù)檢測到 low 小于high此時low=2，high=6，同理R[high] < base ,將R[high] 寫入到R[low]中，low=low+1;從low繼續(xù)探測,low = 3 , high=6 , R[low] > base , 將R[low]寫入到R[high]中，high = high-1;繼續(xù)探測到low小于high此時low=3，high=5，同理R[high] < base,將R[high]寫入到R[low]中，low = low +1；從low繼續(xù)探測，low = 4，high=5，由于R[low] > base , 將R[low]寫入到R[high]中，high = high -1 ;此時探測到low == high == 4 ；該位置即是base所在的位置，將base寫入到該位置中.然后再對子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序，直到Rsi中只有一個元素，或沒有元素。 快速排序的Java實現(xiàn)：private static boolean isEmpty(int[] n) {return n == null || == 0;}// ////////////////////////////////////////////////////** * 快速排序算法思想——挖坑填數(shù)方法： * * @param n 待排序的數(shù)組 */public static void quickSort(int[] n) {if (isEmpty(n))return;quickSort(n, 0, - 1);}public static void quickSort(int[] n, int l, int h) {if (isEmpty(n))return;if (l < h) {int pivot = partion(n, l, h);quickSort(n, l, pivot - 1);quickSort(n, pivot + 1, h);}}private static int partion(int[] n, int start, int end) {int tmp = n[start];while (start < end) {while (n[end] >= tmp && start < end)end--;if (start < end) {n[start++] = n[end];}while (n[start] < tmp && start < end)start++;if (start < end) {n[end--] = n[start];}}n[start] = tmp;return start;}在代碼中有這樣一個函數(shù)：public static void quickSortSwap(int[] n, int l, int h)該函數(shù)可以實現(xiàn)，元素集合中特定的l到h 位置間的數(shù)據(jù)元素進行排序。

pascal改正快速排序，把從小到大改成從大到小，應該怎么改？

首先這個程序不是快速排序。 它是一個遞歸全排列生成的程序。 它是根據(jù)輸入的順序生成的。 只要你輸入 CBA ，輸出就是倒序的了。 你這里沒說清輸入的格式，所以沒法作出改動。 var str:string;l:longint;f:array[1..8]of boolean;//用來記錄每個字母是否用過procedure dfs(dep:longint;ans:string);vari:longint;beginif dep>l then//若l個字母都排好了就打印beginwriteln(ans);exit;end;for i:=1 to l do//檢測每一個字母if f[i]=false then//若第i個字母未用過beginf[i]:=true;//標記此字母已使用dfs(dep+1,ans+str[i]);{將str第i字母選為第dep個字母，再選下一個}f[i]:=false;//返回時將已用過的字母“還掉”不用了end;end;beginreadln(str);l:=length(str);fillchar(f,sizeof(f),0);//標記每個字母都未用過dfs(1,);end.

快速排序算法原理與實現(xiàn)

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

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

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

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

A[i] = A[j];

擴展資料：

快速排序算法 的基本思想是：將所要進行排序的數(shù)分為左右兩個部分，其中一部分的所有數(shù)據(jù)都比另外一 部分的數(shù)據(jù)小，然后將所分得的兩部分數(shù)據(jù)進行同樣的劃分，重復執(zhí)行以上的劃分操作，直 到所有要進行排序的數(shù)據(jù)變?yōu)橛行驗橹埂?

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

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

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

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

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

參考資料:快速排序算法_網(wǎng)絡百科

---

---

相關標簽： 解鎖快速排序怎么弄、 解鎖快速排序的秘密、 從概念到高效實現(xiàn)、

上一篇：快速排序大師課掌握其原理和高級技巧快速排

下一篇：徹底理解快速排序算法步步解剖其內(nèi)幕怎樣才