你應該知道的常用排序算法之快速排序-魔扣目錄

人生有涯，學海無涯

今天跟大家分享一個常用的排序算法——快速排序。我想大家在日常的工作或者面試的時候肯定經常會遇到很多排序算法，而且快速排序算法往往是這里面相對更好的排序算法，并且實現也非常簡單。下面我們一起看下吧。

01、快速排序

我們先看看維基百科的解釋:

快速排序（英語：QuickSort），又稱劃分交換排序（partition-exchange sort），簡稱快排，一種排序算法，最早由東尼·霍爾提出。在平均狀況下，排序 n 個項目要 O(nlogn) 次比較。在最壞狀況下則需要 O(n^2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地達成。

02、算法思想

快速排序的算法思想是分而治之，將一個大的待排序列，分成兩個子序列，然后采用遞歸的方式，依次將子序列也分成更小的子序列，依次進行，最后得到排序好的序列。算法的實現主要分成三步

找到基準點：
排列序列，將比基準點小的放在左邊的子序列，將比基準點大的放在右邊的子序列；
采用遞歸，依次重新選取基準點，在重復進行 1，2 步驟，得到最終的順序序列

03、算法實現

/**
 * <br>
 * <b>Function：</b><br>
 * <b>Author：</b>@author 子悠<br>
 * <b>Date：</b>2019-09-23 01:07<br>
 * <b>Desc：</b>無<br>
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 4, 7, 8, 3, 5, 2, 6, 8, 9, 1};
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    /**
     * 遞歸排序
     *
     * @param array 待排序列
     * @param left  左邊起始位置
     * @param right 右邊結束位置
     */
    private static void quickSort(int[] array, int left, int right) {
        if (left < right) {
            //根據基準點，找到分隔左右子序列的位置索引
            int position = position(array, left, right);
            //分別進行左右的遞歸
            quickSort(array, left, position - 1);
            quickSort(array, position + 1, right);
        }
    }

    /**
     * 找到中間
     *
     * @param array 待排序列
     * @param left  左邊起始位置
     * @param right 右邊結束位置
     * @return
     */
    private static int position(int[] array, int left, int right) {
        //找到基準點, 這里使用的是序列的第一個元素
        int base = array[left];
        while (left < right) {
            while (right > left && array[right] >= base) {
                right--;
            }
            //交互位置
            array[left] = array[right];
            while (left < right && array[left] <= base) {
                left++;
            }
            //交互位置
            array[right] = array[left];
        }
        //此時 left 與 right 是相等的
        array[left] = base;
        return left;
    }
}

運行結果：