快速排序

1. 前言

本節(jié)內(nèi)容是排序算法系列之一：快速排序，主要講解了快速排序的主體思路，選取了一個(gè)待排序的數(shù)字列表對(duì)快速排序算法進(jìn)行了演示，給出了快速排序算法的 Java 代碼實(shí)現(xiàn)，幫助大家可以更好地理解快速排序算法。

2. 什么是快速排序？

快速排序（Quick Sort），是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域中非常經(jīng)典的一種排序算法，應(yīng)用分治思想進(jìn)行排序。

快速排序由于其時(shí)間復(fù)雜度優(yōu)于大部分的排序算法，因而命名為快速排序?？焖倥判?qū)崿F(xiàn)的核心思想就是在待排序序列中選擇一個(gè)基準(zhǔn)值，然后將小于基準(zhǔn)值的數(shù)字放在基準(zhǔn)值左邊，大于基準(zhǔn)值的數(shù)字放在基準(zhǔn)值右邊，然后左右兩邊遞歸排序，整個(gè)排序過(guò)程中最關(guān)鍵部分就是尋找基準(zhǔn)值在待排序序列中的索引位置。

3. 快速排序過(guò)程

在介紹完歸并排序之后，我們一起來(lái)看一下快速排序的實(shí)現(xiàn)步驟具體是什么樣的吧。同樣地，和之前介紹歸并排序時(shí)一樣，這里我們假設(shè)待排序的序列為 [9,2,11,7,12,5]，我們按照從小到大的序列進(jìn)行排序。

3.1 算法描述

快速排序也是應(yīng)用分治法解決問(wèn)題，主要分為以下三步：

1. 步驟 1：

從待排序序列中選擇一個(gè)元素，稱(chēng)之為基準(zhǔn)（pivot)，在這里我們選擇待排序序列中第一個(gè)元素作為基準(zhǔn)。

2. 步驟 2：

對(duì)整個(gè)待排序序列進(jìn)行重新排序，小于基準(zhǔn)的元素放在基準(zhǔn)前面，大于基準(zhǔn)的元素放在基準(zhǔn)后面，基準(zhǔn)放在序列中間，這個(gè)步驟一般稱(chēng)之為分區(qū)操作（partition)。

Tips: 步驟 2 的執(zhí)行其實(shí)就是給基準(zhǔn)元素找到了合適的排序位置。

分區(qū)操作的偽代碼如下，最重要的就是雙指針的應(yīng)用，將待排序序列基于基準(zhǔn)進(jìn)行分區(qū)：

//對(duì)數(shù)組A進(jìn)行一次分區(qū)操作
int pivot = A[0]
low = 0
high = A.length-1
//進(jìn)行分區(qū)操作，找到基準(zhǔn)的位置
while (low < high){
      while(low < high && A[high] >= pivot){
            high = high - 1
      }
      A[low] = A[high]
      while (low < high && A[low] <= pivot){
            low = low + 1
      }
      A[high] = A[low]
}        
//最后賦值基準(zhǔn)
A[low] = pivot

3. 步驟 3：

遞歸的將小于基準(zhǔn)的子序列和大于基準(zhǔn)的子序列進(jìn)行排序。

其實(shí)，上面的排序步驟就是分治法的典型應(yīng)用，選擇基準(zhǔn)分拆序列形成子序列，在子序列中重新排序，完成排序之后進(jìn)行合并，只是因?yàn)樵谶@里完成子序列的排序后待排序序列已經(jīng)完成排序，所以無(wú)需進(jìn)行合并的工作。這里，最需要注意的就是步驟 2 中的分區(qū)操作，這里面會(huì)用到一種最為經(jīng)典的雙指針操作，前后兩個(gè)指針?lè)謩e記錄需要交換的元素位置，后面的代碼示例中會(huì)詳細(xì)說(shuō)明。接下來(lái)，讓我們用上面的待排序數(shù)字隊(duì)列 [9,2,11,7,12,5] 進(jìn)行整個(gè)算法步驟的排序演示工作。

3.2 算法演示

按照 2.1 節(jié)的排序步驟，首先我們從待排序序列中選擇一個(gè)基準(zhǔn) pivot，這里默認(rèn)選擇待排序序列中的第一個(gè)元素，如下：

[9,2,11,7,12,5]   -->  9   //選擇第一個(gè)元素9作為基準(zhǔn)pivot

接著，我們用下圖的示例來(lái)說(shuō)明步驟 2 中的分區(qū)操作，這里用到了雙指針 low 和 high。具體示例如下圖：

按照上圖的示例，可以很清楚地知道，其實(shí)快速排序的本質(zhì)就是把比基準(zhǔn)大的元素都放在基準(zhǔn)數(shù)的右邊，把比基準(zhǔn)小的元素放在基準(zhǔn)數(shù)的左邊，這樣就找到了基準(zhǔn)數(shù)據(jù)在數(shù)組中的正確位置。以后采用遞歸的方式分別對(duì)前半部分和后半部分排序，當(dāng)前半部分和后半部分均有序時(shí)該數(shù)組就自然有序了。如前文中說(shuō)到的快速排序其實(shí)最主要的就是雙指針的應(yīng)用，就是體現(xiàn)在分區(qū)操作時(shí)候的雙指針進(jìn)行分區(qū)。

4.Java 代碼實(shí)現(xiàn)

在說(shuō)明快速排序的整個(gè)過(guò)程之后，接下來(lái)，我們看看如何用 Java 代碼實(shí)現(xiàn)快速排序算法。

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        //初始化需要排序的數(shù)組
        int array[] = {9, 2, 11, 7, 12, 5};
        //快速排序
        quickSort(array,0,array.length-1);
        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

    //快速排序
   private static void quickSort(int[] array,int low, int high){
        if(low < high){
            //找到分區(qū)的位置，左邊右邊分別進(jìn)行快速排序
            int index = partition(array,low,high);
            quickSort(array,0,index-1);
            quickSort(array,index+1,high);
        }
   }

   //快速排序分區(qū)操作
   private static int partition(int[] array, int low, int high){
        //選擇基準(zhǔn)
        int pivot = array[low];
        //當(dāng)左指針小于右指針時(shí)，重復(fù)操作
        while (low < high){
            while(low < high && array[high] >= pivot){
                high = high - 1;
            }
            array[low] = array[high];
            while (low < high && array[low] <= pivot){
                low = low + 1;
            }
            array[high] = array[low];
        }
        //最后賦值基準(zhǔn)
        array[low] = pivot;
        //返回基準(zhǔn)所在位置，基準(zhǔn)位置已經(jīng)排序好
        return low;
   }


}

運(yùn)行結(jié)果如下：

[2, 5, 7, 9, 11, 12]

代碼中的第 8 行初始化一個(gè)需要排序的數(shù)組，后面按照從小到大的排序規(guī)則，實(shí)現(xiàn)了數(shù)組的排序。第 15 行到底 22 行是快速排序的外部結(jié)構(gòu)，應(yīng)用分治思想遞歸求解。代碼 25 行至 43 行是分區(qū)操作，完成基于基準(zhǔn)數(shù)據(jù)的左右分區(qū)，并將基準(zhǔn)數(shù)據(jù)放置在排序好的位置，并且返回基準(zhǔn)所在的位置，進(jìn)行后續(xù)的分治操作。

5. 小結(jié)

本節(jié)主要學(xué)習(xí)了快速排序算法，快速排序是一種非常典型的排序算法，在 Java 程序中，JDK 中的 Arrays.sort() 方法的內(nèi)部實(shí)現(xiàn)就是應(yīng)用到快速排序的思想實(shí)現(xiàn)數(shù)組的排序工作。
在學(xué)習(xí)完本節(jié)課程之后，我們已經(jīng)掌握了排序相關(guān)的基本算法：冒泡排序、插入排序、選擇排序、希爾排序、歸并排序、快速排序。每種排序算法的實(shí)現(xiàn)思路都不相同，對(duì)應(yīng)的算法的時(shí)間復(fù)雜度和空間復(fù)雜度也都不一樣，希望大家可以在學(xué)習(xí)這些基礎(chǔ)排序算法的基礎(chǔ)上多思考，考慮每種排序算法的具體實(shí)現(xiàn)，能夠熟練掌握這些基礎(chǔ)的排序算法。至此，我們也就完成了排序算法的學(xué)習(xí)。