快速排序過(guò)程

沒(méi)有既不浪費(fèi)空間又可以快一點(diǎn)的排序算法呢？那就是“快速排序”！光聽(tīng)這個(gè)名字是不是就覺(jué)得很高端呢。

假設(shè)我們現(xiàn)在對(duì)“52 39 67 95 70 8 25 52'”這個(gè)8個(gè)數(shù)進(jìn)行排序。首先在這個(gè)序列中隨便找一個(gè)數(shù)作為基準(zhǔn)數(shù)（不要被這個(gè)名詞嚇到了，就是一個(gè)用來(lái)參照的數(shù)，待會(huì)你就知道它用來(lái)做啥的了）。為了方便，就讓第一個(gè)數(shù)70作為基準(zhǔn)數(shù)吧。接下來(lái)，需要將這個(gè)序列中所有比基準(zhǔn)數(shù)大的數(shù)放在70的右邊，比基準(zhǔn)數(shù)小的數(shù)放在70的左邊，類(lèi)似下面這種排列：

 8 25 39 52 52' 67 70 95

在初始狀態(tài)下，數(shù)字70在序列的第5位。我們的目標(biāo)是將70挪到序列中間的某個(gè)位置，假設(shè)這個(gè)位置是k?，F(xiàn)在就需要尋找這個(gè)k，并且以第k位為分界點(diǎn)，左邊的數(shù)都小于等于70，右邊的數(shù)都大于等于70。想一想，你有辦法可以做到這點(diǎn)嗎？

基本思想是分治的思想,說(shuō)到分治，就應(yīng)該想到和遞歸是分不開(kāi)的。

有些書(shū)上會(huì)使用關(guān)鍵字比較的表述，有些書(shū)上會(huì)直接使用記錄比較表述，這兩種說(shuō)法是兩個(gè)維度上的說(shuō)法。這里序列元素的關(guān)鍵字屬于記錄的一部分，為了簡(jiǎn)化問(wèn)題，本文的討論并不區(qū)分關(guān)鍵字和記錄，代碼實(shí)現(xiàn)中使用整數(shù)來(lái)表示記錄。簡(jiǎn)而言之，本文的討論簡(jiǎn)化為，對(duì)整型數(shù)組的快速排序。

通過(guò)一趟排序?qū)⒁判虻挠涗浄指畛蓛刹糠?，一部分的關(guān)鍵字值比別一部分的所有關(guān)鍵字都小，然后再依次對(duì)前后兩部分的記錄進(jìn)行快速排序，遞歸該過(guò)程，直到序列中所有記錄都是有序?yàn)橹埂?/p>

步驟

1）分解。選擇第一個(gè)元素作為基準(zhǔn)數(shù)，將輸入序列array[m…n]劃分成兩個(gè)非空序列array[m…k]和array[k+1…n],使array[m…k]中任一元素的值不大于array[k+1…n]任一元素值。

2）遞歸求解。通過(guò)遞歸調(diào)用快排算法分別對(duì)array[m…k]和array[k+1…n]進(jìn)行排序

3）合并。由于對(duì)分解出的兩個(gè)子序列排序都是原地進(jìn)行的,所以在array[m…k]和array[k+1…n]都排好序后不需要再執(zhí)行任何計(jì)算，就能將array[m…n]排好序。因此這一步是不需要在程序中體現(xiàn)的。

排序過(guò)程分析

初始關(guān)鍵字：52 39 67 95 70 8 25 52' ，下面將列出每一趟執(zhí)行的結(jié)果。

基準(zhǔn)52： 52 39 67 95 70 8 25 52'

基準(zhǔn)25： 8 25 39 52 70 95 67 52‘

基準(zhǔn)70： 8 25 39 52 52' 67 70 95

基準(zhǔn)52‘：8 25 39 52 52' 67 70 95

算法分析

快速排序的時(shí)間復(fù)雜度與關(guān)鍵字初始序列有關(guān)。

最壞時(shí)間復(fù)雜度：O(n^2):

以第一個(gè)數(shù)或最后一個(gè)數(shù)為基準(zhǔn)時(shí)，當(dāng)初始序列整體或局部有序時(shí)，快速排序的性能會(huì)下降。若整體有序，此時(shí)，每次劃分只能分出一個(gè)元素，具有最壞時(shí)間復(fù)雜度，快速排序?qū)⑼嘶擅芭菖判颉?/p>

最好時(shí)間復(fù)雜度：

每次選取的基準(zhǔn)關(guān)鍵字都是待排序列的中間值，也就是說(shuō)每次劃分可以將序列劃分為長(zhǎng)度相等的兩個(gè)序列?？焖倥判虻倪f歸過(guò)程可以用一棵二叉樹(shù)來(lái)表示，遞歸樹(shù)的高度是2為底的對(duì)數(shù)，每層需要比較的次數(shù)是n/2，所以最好時(shí)間復(fù)雜度是O(n*以2為底n的對(duì)數(shù))，因?yàn)楹芏鄷r(shí)候輸入序列都是亂序的，所以最好時(shí)間復(fù)雜度也是平均時(shí)間復(fù)雜度。

三種快排和四種優(yōu)化方法

三種快排

這里區(qū)分的方式是不同基準(zhǔn)的選擇方法：

1）固定位置，取第一個(gè)或最后一個(gè)元素作為基準(zhǔn)。這種選取方法不合適局部有序的輸入。

2）隨機(jī)選取基準(zhǔn)，利用隨機(jī)算法，選取待排序序列中任意一個(gè)元素作為基準(zhǔn)。

3）三數(shù)取中，取數(shù)列中第一個(gè)數(shù)，中間位置的數(shù)，最后一個(gè)數(shù)作一個(gè)平均值作為基準(zhǔn)。

四種優(yōu)化

1）當(dāng)排序序列長(zhǎng)度分割到一定程度時(shí)，使用插入排序

對(duì)于N很小或局部有序的數(shù)組，直接插入排序的效率非常高。

2）在一次分割結(jié)束后，可以把與基準(zhǔn)數(shù)相等的元素聚在一起，下次分割時(shí)忽略掉這些元素。

對(duì)于含有重復(fù)元素比較多的序列，這種優(yōu)化方法效果比較好，可以減少很多跌代次數(shù)。

具本過(guò)程：

第一步：在劃分過(guò)程，把與所選取的基準(zhǔn)數(shù)相等的元素放在數(shù)組的兩端。

第二步：劃分結(jié)束后，把兩端的與基準(zhǔn)數(shù)相等的元素移到基準(zhǔn)數(shù)最終位置的兩側(cè)。

3）優(yōu)化遞歸操作。

4）使用多線(xiàn)程并行處理子劃分。

Partition方法在求TopK問(wèn)題上的應(yīng)用

TopK問(wèn)題即求序列中最大或最小的K個(gè)數(shù)。這里以求最小K個(gè)數(shù)為例。

快速排序的思想是使用一個(gè)基準(zhǔn)元素將數(shù)組劃分成兩部分，左側(cè)都比基準(zhǔn)數(shù)小，右側(cè)都比基準(zhǔn)數(shù)大。

給定數(shù)組array[low…h(huán)igh],一趟快排劃分后的結(jié)果有三種：

1）如果基準(zhǔn)數(shù)左側(cè)元素個(gè)數(shù)Q剛好是K-1，那么在基準(zhǔn)數(shù)左側(cè)（包含基準(zhǔn)數(shù)本身），即為T(mén)opK的所有元素。

2）如果基準(zhǔn)數(shù)左側(cè)元素個(gè)數(shù)Q小于K-1,那么說(shuō)明基準(zhǔn)數(shù)左側(cè)的Q個(gè)數(shù)都是TopK里的元素，只需要在基準(zhǔn)數(shù)的右側(cè)找出剩下的K-Q個(gè)元素即可。問(wèn)題轉(zhuǎn)化成了以基準(zhǔn)數(shù)下標(biāo)為起點(diǎn)，高位(high)為終點(diǎn)的Top(K-Q)。遞歸下去即可。

3）如果基準(zhǔn)數(shù)左側(cè)元素個(gè)數(shù)Q大于K-1,說(shuō)明第K個(gè)位置，在基準(zhǔn)數(shù)的左側(cè)，需要縮小搜索范圍，在低位(low)至基準(zhǔn)數(shù)位置重復(fù)遞歸即可，最終問(wèn)題會(huì)轉(zhuǎn)化成上面兩種情況。

快排java實(shí)現(xiàn)

在手寫(xiě)快排算法時(shí)，最好先把一趟排序的過(guò)程寫(xiě)出來(lái)。

package sort;
public class QuickSort {
 // 暴露只一個(gè)參數(shù)的公共接口
 public void quickSort(int a[]) {
 sort(a, 0, a.length - 1);
 }
 // 快排算法的真正實(shí)現(xiàn)
 private void sort(int[] a, int low, int high) {
 if (low >= high)
 return;
 int i = low, j = high; // 設(shè)置這兩個(gè)變量的目的是為了保持low和high不變
 int pivotNum = a[i]; // 基準(zhǔn)數(shù)
 while (i < j) {
 while (a[j] >= pivotNum && j > i) { // 循環(huán)結(jié)束的條件有二：一是找到比支點(diǎn)小的數(shù)，二是j==i
 j--;
 }
 if (j > i) { // 由于上面循環(huán)結(jié)束的功能性有兩個(gè)，對(duì)于找到比支點(diǎn)小的數(shù)，即j!=i，要進(jìn)行位置的交換，下同
 a[i] = a[j];
 i++;
 }
 while (a[i] < pivotNum && i < j) { 
 i++;
 }
 if (i < j) {
 a[j] = a[i];
 j--;
 }
 }
 a[i] = pivotNum;
 sort(a, low, i - 1);
 sort(a, i + 1, high);
 }
 public static void main(String[] args) {
 int[] a = { 52, 39, 67, 95, 70, 8, 25, 52 };
 new QuickSort().quickSort(a);
 for (int i : a) {
 System.out.print(i + " ");
 }
 }
}

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接

最新評(píng)論