北京北大青鳥通州校區(qū)學(xué)術(shù)部老師講解：什么是快速排序？
北京北大青鳥專家解答：快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。最壞情況的時(shí)間復(fù)雜度為O(n2)，最好情況時(shí)間復(fù)雜度為O(nlog2n)。 （北京北大青鳥）
另外 java沒(méi)指針概念 可以認(rèn)為是句柄
假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一躺快速排序。一趟快速排序的算法是： （北京北大青鳥）
1）、設(shè)置兩個(gè)變量I、J，排序開始的時(shí)候I：=1，J：=N；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個(gè)小于X的值，兩者交換；
4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個(gè)大于X的值，兩者交換；
5）、重復(fù)第3、4步，直到I=J；
例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
進(jìn)行第一次交換后： 27 38 65 97 76 13 49
( 按照算法的第三步從后面開始找)
進(jìn)行第二次交換后： 27 38 49 97 76 13 65
( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時(shí)I：=3 )
進(jìn)行第三次交換后： 27 38 13 97 76 49 65
( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找)
進(jìn)行第四次交換后： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時(shí)J：=4 )
此時(shí)再執(zhí)行第三步的時(shí)候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過(guò)一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。 （北京北大青鳥）
快速排序就是遞歸調(diào)用此過(guò)程——在以49為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列，根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過(guò)程：
初始狀態(tài) {49 38 65 97 76 13 27}
進(jìn)行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}
分別對(duì)前后兩部分進(jìn)行快速排序 {13} 27 {38}
結(jié)束 結(jié)束 {49 65} 76 {97}
49 {65} 結(jié)束
結(jié)束
//下面是一個(gè)示例,
public class QuickSort {
/**主方法*/
public static void main(String[] args) {
//聲明數(shù)組
int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5};
//應(yīng)用快速排序方法
quickSort(nums, 0, nums.length-1);
//顯示排序后的數(shù)組
for(int i = 0; i < nums.length; ++i) {
System.out.print(nums[i] + ",");
}
System.out.println("");
}
/**快速排序方法*/
public static void quickSort(int[] a, int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
if (lo >= hi)
return;
//確定指針?lè)较虻倪壿嬜兞?
boolean transfer=true;
while (lo != hi) {
if (a[lo] > a[hi]) {
//交換數(shù)字
int temp = a[lo];
a[lo] = a[hi];
a[hi] = temp;
//決定下標(biāo)移動(dòng)，還是上標(biāo)移動(dòng)
transfer = (transfer == true) ? false : true;
}
//將指針向前或者向后移動(dòng)
if(transfer)
hi--;
else
lo++;
//顯示每一次指針移動(dòng)的數(shù)組數(shù)字的變化
/*for(int i = 0; i < a.length; ++i) {
System.out.print(a[i] + ",");
}
System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
System.out.println("");*/
}
//將數(shù)組分開兩半，確定每個(gè)數(shù)字的正確位置
lo--;
hi++;
quickSort(a, lo0, lo);
quickSort(a, hi, hi0);
}
}
（北京北大青鳥）
相關(guān)鏈接：Java的排序之“堆排序”
