06《算法入门教程》快速排序

1. 前言

本节内容是排序算法系列之一：快速排序，主要讲解了快速排序的主体思路，选取了一个待排序的数字列表对快速排序算法进行了演示，给出了快速排序算法的 Java 代码实现，帮助大家可以更好地理解快速排序算法。

2. 什么是快速排序？

快速排序（Quick Sort），是计算机科学与技术领域中非常经典的一种排序算法，应用分治思想进行排序。

快速排序由于其时间复杂度优于大部分的排序算法，因而命名为快速排序。快速排序实现的核心思想就是在待排序序列中选择一个基准值，然后将小于基准值的数字放在基准值左边，大于基准值的数字放在基准值右边，然后左右两边递归排序，整个排序过程中最关键部分就是寻找基准值在待排序序列中的索引位置。

3. 快速排序过程

在介绍完归并排序之后，我们一起来看一下快速排序的实现步骤具体是什么样的吧。同样地，和之前介绍归并排序时一样，这里我们假设待排序的序列为 [9,2,11,7,12,5]，我们按照从小到大的序列进行排序。

3.1 算法描述

快速排序也是应用分治法解决问题，主要分为以下三步：

1. 步骤 1：

从待排序序列中选择一个元素，称之为基准（pivot)，在这里我们选择待排序序列中第一个元素作为基准。

1. 步骤 2：

对整个待排序序列进行重新排序，小于基准的元素放在基准前面，大于基准的元素放在基准后面，基准放在序列中间，这个步骤一般称之为分区操作（partition)。

Tips: 步骤 2 的执行其实就是给基准元素找到了合适的排序位置。

分区操作的伪代码如下，最重要的就是双指针的应用，将待排序序列基于基准进行分区：

//对数组A进行一次分区操作
int pivot = A[0]
low = 0
high = A.length-1
//进行分区操作，找到基准的位置
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

1. 步骤 3：

递归的将小于基准的子序列和大于基准的子序列进行排序。

其实，上面的排序步骤就是分治法的典型应用，选择基准分拆序列形成子序列，在子序列中重新排序，完成排序之后进行合并，只是因为在这里完成子序列的排序后待排序序列已经完成排序，所以无需进行合并的工作。这里，最需要注意的就是步骤 2 中的分区操作，这里面会用到一种最为经典的双指针操作，前后两个指针分别记录需要交换的元素位置，后面的代码示例中会详细说明。接下来，让我们用上面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

3.2 算法演示

按照 2.1 节的排序步骤，首先我们从待排序序列中选择一个基准 pivot，这里默认选择待排序序列中的第一个元素，如下：

[9,2,11,7,12,5]   -->  9   //选择第一个元素9作为基准pivot

接着，我们用下图的示例来说明步骤 2 中的分区操作，这里用到了双指针 low 和 high。具体示例如下图：

5ed5fa5608c7309f07791600.jpg

按照上图的示例，可以很清楚地知道，其实快速排序的本质就是把比基准大的元素都放在基准数的右边，把比基准小的元素放在基准数的左边，这样就找到了基准数据在数组中的正确位置。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。如前文中说到的快速排序其实最主要的就是双指针的应用，就是体现在分区操作时候的双指针进行分区。

4.Java 代码实现

在说明快速排序的整个过程之后，接下来，我们看看如何用 Java 代码实现快速排序算法。

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        //初始化需要排序的数组
        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){
            //找到分区的位置，左边右边分别进行快速排序
            int index = partition(array,low,high);
            quickSort(array,0,index-1);
            quickSort(array,index+1,high);
        }
   }

   //快速排序分区操作
   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;
        //返回基准所在位置，基准位置已经排序好
        return low;
   }


}

运行结果如下：

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

代码中的第 8 行初始化一个需要排序的数组，后面按照从小到大的排序规则，实现了数组的排序。第 15 行到底 22 行是快速排序的外部结构，应用分治思想递归求解。代码 25 行至 43 行是分区操作，完成基于基准数据的左右分区，并将基准数据放置在排序好的位置，并且返回基准所在的位置，进行后续的分治操作。

5. 小结

本节主要学习了快速排序算法，快速排序是一种非常典型的排序算法，在 Java 程序中，JDK 中的 Arrays.sort() 方法的内部实现就是应用到快速排序的思想实现数组的排序工作。
在学习完本节课程之后，我们已经掌握了排序相关的基本算法：冒泡排序、插入排序、选择排序、希尔排序、归并排序、快速排序。每种排序算法的实现思路都不相同，对应的算法的时间复杂度和空间复杂度也都不一样，希望大家可以在学习这些基础排序算法的基础上多思考，考虑每种排序算法的具体实现，能够熟练掌握这些基础的排序算法。至此，我们也就完成了排序算法的学习。