快速排序是對冒泡排序的一種改進(jìn)，是所有內(nèi)部排序算法中平均性能最優(yōu)的排序算法。其基本思想是基于分治法的：在待排序數(shù)組L[1...n]中任取一個元素pivot作為基準(zhǔn)，從數(shù)組的兩端開始掃描。設(shè)兩個指示標(biāo)志（low指向起始位置，high指向末尾)，先從后向前掃描（high遞減），如果high位置的元素小于pivot，就交換low和high位置的元素，然后從前向后掃描（low遞增），如果low位置的元素大于pivot，就交換low和high位置的元素。重復(fù)上述過程，直到low>=high，然后把基準(zhǔn)放到low位置上，一趟排序就完成了，將一個元素（基準(zhǔn)）放到了最終位置上，不產(chǎn)生有序子序列。將待排序數(shù)組劃分為兩部分即L[1...k-1]和L[k+1...n]，使得前半部分L[1...k-1]所有元素小于pivot，后半部分L[k+1...n]所有元素大于或等于pivot。接著采用遞歸的方式分別對前半部分和后半部分排序，直到每部分只有一個元素或空為止，即所有元素放在了最終位置上。

　　之所以快速排序比較快，是因為相比于冒泡排序，每次交換是跳躍式的。每次排序時選取一個基準(zhǔn)，將小于基準(zhǔn)的數(shù)全部放到基準(zhǔn)點(diǎn)的左邊，將大于或等于基準(zhǔn)的數(shù)全部放到基準(zhǔn)的右邊，在每次交換時不會像冒泡排序一樣只能在相鄰的數(shù)之間進(jìn)行交換，增大了交換距離，減少了總的比較和交換次數(shù)，加快了速度。在最壞情況下，仍可能交換相鄰的兩個數(shù)。

　　假設(shè)對“6 1 2 7 9 3 4 5 10 8”這10個數(shù)進(jìn)行排序：

　　從后向前掃描

　　

　　交換7和5

　　

　　交換之后：6 1 2 5 9 3 4 7 10 8

　　交換9和4

　　

　　交換之后：6 1 2 5 4 3 9 7 10 8

　　i>=j，交換6和3

　　

　　交換之后：3 1 2 5 4 6 9 7 10 8

　　一趟排序結(jié)束。

1 public class QuickSort { 2 3 public static void quickSort(int[] arr, int low, int high) { 4 // 至少有兩個元素需要排序 5 if (low < high) { 6 int curLow = low; 7 int curHigh = high; 8 int temp = arr[low]; 9 10 while(curLow < curHigh) { 11 // 從右向左掃描，尋找第一個比基準(zhǔn)小的數(shù) 12 while(curLow < curHigh && arr[curHigh] >= temp) { 13 curHigh--; 14 } 15 arr[curLow] = arr[curHigh]; 16 17 // 從左向右掃描，尋找第一個比基準(zhǔn)大的數(shù) 18 while(curLow < curHigh && arr[curLow] <= temp) { 19 curLow++; 20 } 21 arr[curHigh] = arr[curLow]; 22 } 23 24 // 基準(zhǔn)歸位 25 arr[curLow] = temp; 26 27 // 基準(zhǔn)位置左邊子序列遞歸排序 28 quickSort(arr, low, curLow - 1); 29 // 基準(zhǔn)位置左邊子序列遞歸排序 30 quickSort(arr, curLow + 1, high); 31 } 32 } 33 34 public static void main(String[] args) { 35 int[] arr = {15, 1, 17, 3, 6, 8}; 36 QuickSort.quickSort(arr, 0, arr.length - 1); 37 38 for (int i = 0, length = arr.length; i < length; i++) { 39 System.out.printf(" %d", arr[i]); 40 } 41 } 42 43 }

　　結(jié)果如下：

1 3 6 8 15 17

　　上述代碼每次以當(dāng)前數(shù)組中第一個元素作為基準(zhǔn)對數(shù)組進(jìn)行劃分。

　　快速排序性能分析：

　　空間復(fù)雜度：因為快速排序是遞歸的，所以需要借助一個遞歸工作棧來保存每一層遞歸調(diào)用的必要信息，容量應(yīng)與遞歸調(diào)用的最大深度一致。最壞情況下n-1次遞歸調(diào)用，棧的深度為O(n)；最好和平均情況下棧的深度為O(log₂n)。所以，空間復(fù)雜度在最壞情況下為O(n)，平均情況下為O(log₂n)。

　　時間復(fù)雜度：快速排序的性能主要取決于劃分操作的好壞。最壞情況下待排序數(shù)組基本有序或基本逆序時，每一次遞歸劃分的兩個區(qū)域分別包含n-1個元素和0個元素，快速排序退化成冒泡排序，時間復(fù)雜度為O(n²)。最好情況下最平衡劃分，兩個子數(shù)組長度不超過n/2，時間復(fù)雜度為O(nlog₂n)。而快速排序平均情況下運(yùn)行時間接近于最好情況下的運(yùn)行時間，即時間復(fù)雜度在最壞情況下為O(n²)，平均情況下為O(nlog₂n)。

　　穩(wěn)定性：如果右端區(qū)間有兩個相同的關(guān)鍵字，且均小于基準(zhǔn)，那么交換到左端區(qū)間后，它們的相對次序會變化，即快速排序不穩(wěn)定。例如，表L={3， 2， 2}，經(jīng)過一趟排序后L={2， 2， 3}，最終結(jié)果是L={2，?2， 3}，2與2的相對次序發(fā)生了變化。

　　改進(jìn)方案

　　1 使用直接插入排序

　　當(dāng)遞歸過程中劃分得到的子數(shù)組長度較小時，可以使用直接插入排序完成排序工作。

1 public static void quick(int []array ,int lo,int hi){ 2 if(hi-lo+1<10){ 3 insertSort(array); 4 }else{ 5 quickSort(array,lo,hi); 6 } 7 }

　　2 選取好的基準(zhǔn)

　　盡量選取可以把元素平衡劃分的基準(zhǔn)，有三種方法：固定切分，隨機(jī)切分和三取樣切分。固定切分的效率低。隨機(jī)切分是常用的一種切分，效率高，最壞情況下時間復(fù)雜度有可能為O(n²)。三取樣切分最理想，具體操作：選取數(shù)組的頭尾和中間這3個元素，取這3個元素的中間值作為基準(zhǔn)。

1 public static int partition(int []array,int lo,int hi){ 2 //三數(shù)取中 3 int mid=lo+(hi-lo)/2; 4 if(array[mid]>array[hi]){ 5 swap(array[mid],array[hi]); 6 } 7 if(array[lo]>array[hi]){ 8 swap(array[lo],array[hi]); 9 } 10 if(array[mid]>array[lo]){ 11 swap(array[mid],array[lo]); 12 } 13 int key=array[lo]; 14 15 while(lo<hi){ 16 while(array[hi]>=key&&hi>lo){ 17 hi--; 18 } 19 array[lo]=array[hi]; 20 while(array[lo]<=key&&hi>lo){ 21 lo++; 22 } 23 array[hi]=array[lo]; 24 } 25 array[hi]=key; 26 return hi; 27 } 28 29 public static void swap(int a,int b){ 30 int temp=a; 31 a=b; 32 b=temp; 33 } 34 public static void sort(int[] array,int lo ,int hi){ 35 if(lo>=hi){ 36 return ; 37 } 38 int index=partition(array,lo,hi); 39 sort(array,lo,index-1); 40 sort(array,index+1,hi); 41 }

　　

　　參考資料

　　《2017年數(shù)據(jù)結(jié)構(gòu)聯(lián)考復(fù)習(xí)指導(dǎo)》 P287-288

　　快速排序（java實現(xiàn)）

　　坐在馬桶上看算法：快速排序

轉(zhuǎn)載于:https://www.cnblogs.com/WJQ2017/p/8340156.html

總結(jié)

以上是生活随笔為你收集整理的数据结构 快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。