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

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

??????? 具體做法是：假設(shè)要對(duì)某個(gè)數(shù)組進(jìn)行排序，首先需要任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它的前面，所有比它大的數(shù)都放到它的后面。這個(gè)過程稱為一趟快速排序；遞歸調(diào)用此過程，即可實(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--;
        }
        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)行測試，輸出結(jié)果如下：

排序前：
13 15 24 99 14 11 1 2 3
排序后：
1 2 3 11 13 14 15 24 99 

文章來源地址http://www.zghlxwxcb.cn/news/detail-507620.html

到了這里，關(guān)于第三十三章Java快速排序法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！