快 速排序(Quicksort)是對(duì)冒泡排序的一種改進(jìn)，是一種排序執(zhí)行效率很高的排序算法。

　　快 速排序的基本思想是：通過(guò)一趟排序，將要排序的數(shù)據(jù)分隔成獨(dú)立的兩部分，其中一部分的所 有數(shù)據(jù)比另外一部分的所 有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快 速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此使整個(gè)數(shù)據(jù)變成有序序列。

　　具體做法是：假設(shè)要對(duì)某個(gè)數(shù)組進(jìn)行排序，首先需要任意選取一個(gè)數(shù)據(jù)(通常選用第  一個(gè)數(shù)據(jù))作為關(guān)鍵數(shù)據(jù)，然后將所 有比它小的數(shù)都放到它的前面，所 有比它大的數(shù)都放到它的后面。這個(gè)過(guò)程稱為一趟快 速排序;遞歸調(diào)用此過(guò)程，即可實(shí)現(xiàn)數(shù)據(jù)的快 速排序。

　　例 1

　　利用快 速排序法對(duì)一數(shù)組進(jìn)行排序，實(shí)現(xiàn)步驟如下。

　　(1) 聲明靜態(tài)的 getMiddle() 方法，該方法需要返回一個(gè) int 類型的參數(shù)值，在該方法中傳入 3 個(gè)參數(shù)。代碼如下：

　　public static int getMiddle(int[] list, int low, int high) {

　　int tmp = list[low]; // 數(shù)組的第 一個(gè)值作為中軸(分界點(diǎn)或關(guān)鍵數(shù)據(jù))

　　while (low < high) {

　　while (low < high && list[high] > tmp) {

　　high--;

　　填寫(xiě)下面表單即可預(yù)約申請(qǐng)免費(fèi)試聽(tīng)java課程!害怕學(xué)不會(huì)?助教陪讀，隨時(shí)解惑!擔(dān)心就業(yè)?一地學(xué)習(xí)，可全國(guó)推薦就業(yè)!

　　}

　　list[low] = list[high]; // 比中軸小的記錄移到低端

　　while (low < high && list[low] < tmp) {

　　low++;

　　}

　　list[high] = list[low]; // 比中軸大的記錄移到高端

　　}

　　list[low] = tmp; // 中軸記錄到尾

　　return low; // 返回中軸的位置

　　}

　　(2) 創(chuàng)建靜態(tài)的 unckSort() 方法，在該方法中判斷 low 參數(shù)是否小于 high 參數(shù)，如果是則調(diào)用 getMiddle() 方法，將數(shù)組一分為二，并且調(diào)用自身的方法進(jìn)行遞歸排序。代碼如下：

　　public static void unckSort(int[] list,int low,int high) {

　　if(low < high) {

　　int middle = getMiddle(list,low,high); // 將list數(shù)組一分為二

　　unckSort(list,low,middle-1); // 對(duì)低字表進(jìn)行遞歸排序

　　unckSort(list,middle+1,high); // 對(duì)高字表進(jìn)行遞歸排序

　　}

　　}

　　(3) 聲明靜態(tài)的 quick() 方法，在該方法中判斷傳入的數(shù)組是否為空，如果不為空，則調(diào)用 unckSort() 方法進(jìn)行排序。代碼如下：

　　public static void quick(int[] str) {

　　if(str.length > 0) {

　　// 查看數(shù)組是否為空

　　unckSort(str,0,str.length-1);

　　}

　　}

　　(4) 在 main() 方法中聲明 int 類型的 number 數(shù)組，接著輸出該數(shù)組中的元素。然后調(diào)用自定義的 quick() 方法進(jìn)行排序，排序后重新輸出數(shù)組中的元素。代碼如下：

　　int[] number={13,15,24,99,14,11,1,2,3};

　　System.out.println("排序前：");

　　for(int val:number) {

　　System.out.print(val+" ");

　　}

　　quick(number);

　　System.out.println("\n排序后：");

　　for(int val:number) {

　　System.out.print(val +" ");

　　}

　　運(yùn)行前面的代碼進(jìn)行測(cè)試，輸出結(jié)果如下：

　　排序前：

　　13 15 24 99 14 11 1 2 3

　　排序后：

　　1 2 3 11 13 14 15 24 99