快速排序算法是冒泡排序算法的一種改進(jìn)，采用“分而治之”的思想，把大的拆分成小的，再把小的拆分成更小的。如：對(duì)于一組待排的記錄，通過(guò)一趟排序后，將原序列分成兩部分，其中前一部分的所有記錄均比后一部分的所有記錄小，然后再依次對(duì)前后兩部分的記錄進(jìn)行快速排序，遞歸該過(guò)程，直到序列中的所有記錄均有序?yàn)橹埂?br /> 具體而言，其算法步驟如下：
（1） 分解。將輸入的序列a[m…n]劃分成兩個(gè)非空子序列a[m…k]和a[k+1…n]，使a[m…k]中任一元素的值不大于a[k+1…n]中的任一元素。
（2） 遞歸求解。通過(guò)遞歸調(diào)用快速排序算法分別對(duì)a[m…n]和a[k+1…n]進(jìn)行排序。
（3） 合并。由于對(duì)分解出的兩個(gè)子序列的排序是就地進(jìn)行的，所以在a[m…k]和a[k+1…n都排好序后不需要執(zhí)行任何計(jì)算array[m…n]就已排好序。
以數(shù)組{38,65,97,76,13,27,49}為例：
第一趟選取的關(guān)鍵字是38，則對(duì)應(yīng)的，第一趟排序的結(jié)果是：[27 13] 38 [76 97 65 49]；
第二趟排序：
對(duì)于38左側(cè)部分[27 13]進(jìn)行快速排序，選取的關(guān)鍵字是27，排序結(jié)果是[13] 27，
對(duì)于28右側(cè)部分[76 97 65 49]進(jìn)行快速排序，選取的關(guān)鍵字是76，排序結(jié)果是[49 65] 76 [97]，
因此，第二趟排序的結(jié)果是[13] 27 [49 65] 76 [97]
第三趟排序：
對(duì)于27左側(cè)部分[13]，只剩一個(gè)元素，則無(wú)需排序，同時(shí)，27右側(cè)沒(méi)有元素
對(duì)于76左側(cè)元素排序[49 65]，進(jìn)行快速排序，選取關(guān)鍵字為49，排序結(jié)果為49 [65]
對(duì)于76右側(cè)的元素[97]，只有一個(gè)元素，則無(wú)需排序，
因此，第三趟排序的結(jié)果是13 27 49 [65] 76 97
而最終的排序結(jié)果是13 27 49 65 76 97
相對(duì)應(yīng)的代碼實(shí)現(xiàn)如下：
public class Test {
public static void main(String[] args){
int[] a = {38,65,97,76,13,27,49};
quickSort(a);
for (int i = 0; i < a.length; i ++){
System.out.print( a[i] + “\t” );
}
}

private static void quickSort(int[] a) {sort(0,a.length-1,a); }private static void sort(int low, int high, int[] a) {if (low >= high){return;}int i = low;int j = high;int index = a[i];while(i < j){while(i < j && a[j] >= index){j--;}if (i < j){a[i++] = a[j];}while(i < j && a[i] <= index){i++;}if (i < j){a[j--] = a[i];}}a[i] = index;sort(low,i-1,a);sort( i+1,high,a ); }

}

以上是對(duì)快速排序算法的分析，對(duì)于快速排序算法復(fù)雜度分析如下：
（1） 最好的時(shí)間復(fù)雜度。最好的情況是每次區(qū)間劃分的結(jié)果都是關(guān)鍵字左右兩邊的序列長(zhǎng)度相等或者相差為1，即選擇的關(guān)鍵字為待排記錄中的中間值，此時(shí)，進(jìn)行的比較次數(shù)總共為nlogn，即，最好的時(shí)間復(fù)雜度為O(nlogn)
（2） 最壞時(shí)間復(fù)雜度。最壞情況是每次區(qū)間劃分的結(jié)果都是關(guān)鍵字的左邊或者右邊，而另一邊區(qū)間中的待排記錄僅比排序前少了一個(gè)，即選擇的關(guān)鍵字是待排記錄中的最小值或者最大值，總共需要比較的次數(shù)為n(n-1)/2，所以，在最壞情況下快速排序的時(shí)間復(fù)雜度為O(n*n)。
（3） 平均時(shí)間復(fù)雜度。快速排序的平均時(shí)間復(fù)雜度為O(nlogn)。
快速排序具有不穩(wěn)定性，待排記錄長(zhǎng)度較大時(shí)，比較好

總結(jié)

以上是生活随笔為你收集整理的快速排序算法原理详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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