快速排序

1. 前言

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

2. 什么是快速排序？

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

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

3. 快速排序過程

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

3.1 算法描述

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

1. 步驟 1：

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

2. 步驟 2：

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

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

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

//對數(shù)組A進行一次分區(qū)操作
int pivot = A[0]
low = 0
high = A.length-1
//進行分區(qū)操作，找到基準的位置
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]
}        
//最后賦值基準
A[low] = pivot

3. 步驟 3：

遞歸的將小于基準的子序列和大于基準的子序列進行排序。

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

3.2 算法演示

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

[9,2,11,7,12,5]   -->  9   //選擇第一個元素9作為基準pivot

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

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

4.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ū)的位置，左邊右邊分別進行快速排序
            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){
        //選擇基準
        int pivot = array[low];
        //當左指針小于右指針時，重復操作
        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];
        }
        //最后賦值基準
        array[low] = pivot;
        //返回基準所在位置，基準位置已經(jīng)排序好
        return low;
   }


}

運行結果如下：

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

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

5. 小結

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