本文首發(fā)自「慕課網(wǎng)」，想了解更多IT干貨內(nèi)容，程序員圈內(nèi)熱聞，歡迎關(guān)注！

作者| 慕課網(wǎng)精英講師 JdreamZhang

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

【資料圖】

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

1. 快速排序過程

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

1.1 算法描述

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

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

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

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

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

//對數(shù)組A進(jìn)行一次分區(qū)操作int pivot = A[0]low = 0high = 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代碼塊1234567891011121314151617

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

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

1.2 算法演示

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

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

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

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

2.Java 代碼實現(xiàn)

在說明快速排序的整個過程之后，接下來，我們看看如何用 Java 代碼實現(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)左指針小于右指針時，重復(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;   }}代碼塊12345678910111213141516171819202122232425262728293031323334353637383940414243444546

運行結(jié)果如下：

[2, 5, 7, 9, 11, 12]代碼塊1

代碼中的第 8 行初始化一個需要排序的數(shù)組，后面按照從小到大的排序規(guī)則，實現(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ù)的分治操作。

3. 小結(jié)

本篇文章主要幫大家介紹了快速排序算法，快速排序是一種非常典型的排序算法，在 Java 程序中，JDK 中的Arrays.sort()方法的內(nèi)部實現(xiàn)就是應(yīng)用到快速排序的思想實現(xiàn)數(shù)組的排序工作。

對于算法，其實每種排序算法的實現(xiàn)思路都不相同，對應(yīng)的算法的時間復(fù)雜度和空間復(fù)雜度也都不一樣，希望大家可以在學(xué)習(xí)這些基礎(chǔ)排序算法的基礎(chǔ)上多思考，考慮每種排序算法的具體實現(xiàn)，能夠熟練掌握這些基礎(chǔ)的排序算法。

歡迎關(guān)注「慕課網(wǎng)」，發(fā)現(xiàn)更多IT圈優(yōu)質(zhì)內(nèi)容，分享干貨知識，幫助你成為更好的程序員！