JAVA十大排序算法之快速排序詳解

更新時間：2021年08月23日 10:32:13 作者：阿粵Ayue

這篇文章主要介紹了java中的快速排序，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下

快速排序

快速排序是對冒泡排序的一種改進，也是采用分治法的一個典型的應用。JDK中Arrays的sort()方法，具體的排序細節(jié)就是使用快速排序實現(xiàn)的。

從數(shù)組中任意選取一個數(shù)據(jù)（比如數(shù)組的第一個數(shù)或最后一個數(shù)）作為關鍵數(shù)據(jù)，我們稱為基準數(shù)(pivot，或中軸數(shù))，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序，也稱為分區(qū)（partition）操作。

問題

若給定一個無序數(shù)組 [8, 5, 6, 4, 3, 1, 7, 2]，并指定一個數(shù)為基準，拆分數(shù)組使得左側的數(shù)都小于等于它，右側的數(shù)都大于它。

基準的選取最優(yōu)的情況是基準值剛好取在無序區(qū)數(shù)值的中位數(shù)，這樣能夠最大效率地讓兩邊排序，同時最大地減少遞歸劃分的次數(shù)，但是一般很難做到最優(yōu)?；鶞实倪x取一般有三種方式：

選取數(shù)組的第一個元素
選取數(shù)組的最后一個元素
以及選取第一個、最后一個以及中間的元素的中位數(shù)（如4 5 6 7, 第一個4, 最后一個7, 中間的為5, 這三個數(shù)的中位數(shù)為５, 所以選擇5作為基準）。

思路

隨機選擇數(shù)組的一個元素，比如 6 為基準，拆分數(shù)組同時引入一個初始指針，也叫分區(qū)指示器，初始指針指向 -1
將數(shù)組中的元素和基準數(shù)遍歷比較
若當前元素大于基準數(shù)，不做任何變化
若當前元素小于等于基準數(shù)時，分割指示器右移一位，同時
- 當前元素下標小于等于分區(qū)指示器時，當前元素保持不動
- 當前元素下標大于分區(qū)指示器時，當前元素和分區(qū)指示器所指元素交換

快速排序

荷蘭國旗問題

荷蘭的國旗是由紅白藍三種顏色構成，如圖：

若現(xiàn)在給一個隨機的圖形，如下：

把這些條紋按照顏色排好，紅色的在上半部分，白色的在中間部分，藍色的在下半部分，這類問題稱作荷蘭國旗問題。

對應leetcode：顏色分類

給定一個包含紅色、白色和藍色，一共 n 個元素的數(shù)組，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。

分析：

假如給定一個數(shù)組[8, 3, 6, 2, 5, 1, 7, 5]，做如下操作：

1.隨機選擇數(shù)組的一個元素，比如 5 為基準，拆分數(shù)組同時引入一個左分區(qū)指示器，指向 -1，右分區(qū)指示器指向基準數(shù)（注：此時的基準數(shù)為尾元素）

2.若當前元素大于基準數(shù)，右分區(qū)指示器左移一位，當前元素和右分區(qū)指示器所指元素交換，

索引保持不變

3.若當前元素小于等于基準數(shù)時，左分區(qū)指示器右移一位，索引右移

當前元素大于等于左分區(qū)指示器所指元素，當前元素保持不動
當前元素小于左分區(qū)指示器所指元素，交換

簡單來說就是，左分區(qū)指示器向右移動的過程中，如果遇到大于或等于基準數(shù)時，則停止移動，右分區(qū)指示器向左移動的過程中，如果遇到小于或等于主元的元素則停止移動。這種操作也叫雙向快速排序。

345345

代碼實現(xiàn)

public class QuickSort {
    public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};
    private static int[] sort(int[] array, int left, int right) {
        if (array.length < 1 || left > right) return null;
        //拆分
        int partitionIndex = partition(array, left, right);
        //遞歸
        if (partitionIndex > left) {
            sort(array, left, partitionIndex - 1);
        }
        if (partitionIndex < right) {
            sort(array, partitionIndex + 1, right);
        }
        return array;
    }
    /**
     * 分區(qū)快排操作
     *
     * @param array 原數(shù)組
     * @param left  左側頭索引
     * @param right 右側尾索引
     * @return 分區(qū)指示器  最后指向基準數(shù)
     */
    public static int partition(int[] array, int left, int right) {
        //基準數(shù)下標---隨機方式取值，也就是數(shù)組的長度隨機1-8之間
        int pivot = (int) (left + Math.random() * (right - left + 1));
        //分區(qū)指示器索引
        int partitionIndex = left - 1;
        //基準數(shù)和尾部元素交換
        swap(array, pivot, right);
        //按照規(guī)定，如果當前元素大于基準數(shù)不做任何操作；
        //小于基準數(shù)，分區(qū)指示器右移，且當前元素的索引大于分區(qū)指示器，交換
        for (int i = left; i <= right; i++) {
            if (array[i] <= array[right]) {//當前元素小于等于基準數(shù)
                partitionIndex++;
                if (i > partitionIndex) {//當前元素的索引大于分區(qū)指示器
                    //交換
                    swap(array, i, partitionIndex);
                }
            }
        }
        return partitionIndex;
    }
    /**
     * 雙向掃描排序
     */
    public static int partitionTwoWay(int[] array, int left, int right) {
        //基準數(shù)
        int pivot = array[right];
        //左分區(qū)指示器索引
        int leftIndex = left - 1;
        //右分區(qū)指示器索引
        int rightIndex = right;
        //索引
        int index = left;
        while (index < rightIndex) {
            //若當前元素大于基準數(shù)，右分區(qū)指示器左移一位，當前元素和右分區(qū)指示器所指元素交換，索引保持不變
            if (array[index] > pivot) {
                swap(array, index, --rightIndex);
            } else if (array[index] <= pivot) {//當前元素小于等于基準數(shù)時，左分割指示器右移一位，索引右移
                leftIndex++;
                index++;
                //當前元素小于等于左分區(qū)指示器所指元素，交換
                if (array[index] < array[leftIndex]) {
                    swap(array, index, leftIndex);
                }
            }
        }
        //索引和 L 指向同一個元素
        swap(array, right, rightIndex);
        return 1;
    }
    //交換
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY, 0, ARRAY.length - 1));
        System.out.println("====================雙向排序==================");
        print(ARRAY2);
        System.out.println("============================================");
        print(sort(ARRAY2, 0, ARRAY2.length - 1));
    }
}