经典算法学习之------快速排序

一、什么是算法

本专栏为《手撕算法》栏目的子专栏：《经典算法》，会讲述一些经典算法，并进行分析。在此之前我们要先了解什么是算法，能够解决什么样的问题。

1. 算法的定义

以下为经典教材《Introduction.to.Algorithms》开篇中的内容。

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

可以看到，任何被明确定义的计算过程都可以称作算法，它将某个值或一组值作为输入，并产生某个值或一组值作为输出。所以算法可以被称作将输入转为输出的一系列的计算步骤。

这样的概括是比较标准和抽象的，其实说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码来表示，清晰的表达出思路和步骤，这样在真正执行的时候，就可以使用不同的语言来实现出相同的效果。

概括的说，算法就是解决问题的工具。在描述一个算法时，我们关注的是输入与输出。也就是说只要把原始数据和结果数据描述清楚了，那么算法所做的事情也就清楚了。我们在设计一个算法时也是需要先明确我们有什么和我们要什么，这一点相信大家在后面的文章中会慢慢体会到。

2. 补充的概念

数据结构

算法经常会和数据结构一起出现，这是因为对于同一个问题（如：排序），使用不同的数据结构来存储数据，对应的算法可能千差万别。所以在整个学习过程中，也会涉及到各种数据结构的使用。

常见的数据结构包括：数组、堆、栈、队列、链表、树等等。

算法的效率

在一个算法设计完成后，还需要对算法的执行情况做一个评估。一个好的算法，可以大幅度的节省运行的资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准来确定一个量级，通常会使用到时间复杂度和空间复杂度这两个概念。

时间复杂度

通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T(n)，它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。

对于每一段代码，都可以转化为常数或与n相关的函数表达式，记做f(n) 。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度，记做O(f(n)) ，其中的O就是代表数量级。

常见的时间复杂度有（由低到高）：O(1)、O( log ⁡ 2 n \log _{2} n log2n)、O(n)、O( n log ⁡ 2 n n\log _{2} n nlog2n)、O( n 2 n^{2} n2)、O( n 3 n^{3} n3)、O( 2 n 2^{n} 2n)、O(n!)。

空间复杂度

程序从开始执行到结束所需要的内存容量，也就是整个过程中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注算法运行时需要额外定义多少临时变量或多少存储结构。如：如果需要借助一个临时变量来进行两个元素的交换，则空间复杂度为O(1)。

伪代码约定

伪代码是用来描述算法执行的步骤，不会具体到某一种语言，为了表达清晰和标准化，会有一些约定的含义：

缩进：表示块结构，如循环结构或选择结构，使用缩进来表示这一部分都在该结构中。

循环计数器：对于循环结构，在循环终止时，计数器的值应该为第一个超出界限的值。

to：表示循环计数器的值增加。

downto：表示循环计数器的值减少。

by：循环计数器的值默认变化量为1，当大于1时可以使用by。

变量默认是局部定义的。

数组元素访问：通过"数组名[下标]"形式，在伪代码中，下标从1开始（"A[1]“代表数组A的第一个元素）。

子数组：使用”…"来代表数组中的一个范围，如"A[i…j]"代表从第i个到第j个元素组成的子数组。

对象与属性：复合的数据会被组织成对象，如链表包含后继（next）和存储的数据（data）,使用“对象名 + 点 + 属性名”。

特殊值NIL：表示指针不指向任何对象，如二叉树节点无子孩子可认为左右子节点信息为NIL。

return：返回到调用过程的调用点，在伪代码中允许返回多个值。

and和or：与运算和或运算默认短路，即如果已经能够确定表达式结果时，其他条件不会去判断或执行。

二、交换排序

1. 交换排序介绍

交换排序的核心思想是，每次将元素两两比较，如果不满足正确的相对序列（如：较小的应该在前）则进行交换。不断的根据某个规律进行比较和交换，直到全部满足为止，此时也就得到了一个有序的序列。

冒泡排序

也称气泡排序，是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对儿元素进行交换，再进行下一对儿元素的比较。每一趟冒泡后，就会送一个最小的元素达到最上端。在无序区中重复这个过程，直到所有的元素有序。\

快速排序

快速排序是冒泡排序的改进算法，主要思想是在待排序列中取一个元素（通常为第一个）作为参照，将序列分为两个子序列，比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位，并得到两个子序列。在子序列中继续执行该步骤，直到子序列的长度为0或1。

2. 快速排序

输入

n个数的序列，通常直接存放在数组中，可能是任何顺序。

输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。

算法说明

快速排序是一种划分交换排序方法，采用了分治策略。首先将原问题划分成若干个规模更小、与原问题相似的子问题，然后用递归方法解决这些子问题，最后再将它们组合成原问题的解。

第一趟排好序列中的一个数，放在它应该在的位置上，同时得到两个子序列，左侧都是比它小的数，右侧都是比它大的数（升序排序时）。接下来在每个子序列中不断重复归位一个元素、得到子序列这个过程，直到子序列的长度为1或0，此时整体的序列已经有序。

算法流程

以下为第一趟排序的过程，选定一个待排元素x后，不断缩小无限制区域，使得得到的两个子序列（两个区域）满足其中一个都比x小，另一个都比x大，最后将待排元素插入到两个区间中间即完成排序（暂不考虑存在相同元素）。\

以下图片取材自《算法导论》，完成第一趟排序后，不断的在得到的子序列中重复该步骤：\

（a）将待排元素选定为序列的最后一个元素：4，目标是在左侧的无序区中划分出两个子序列。

p为序列区间左端点，r为序列区间右端点。

i的初始值在区间端点之前，用于划分出较小元素所在区间。

j为进行扫描时使用的变量，每次取到元素进行判断，然后进行区间的调整。

p与i之间的部分构成浅色区域（较小数区间），i与j之间的部分构成深色区域（较大数区间）。

（b）2 < 4，应归入较小数区间，i进行后移（此时i与j指向同一元素），并与j指向的元素交换，浅色区域增加。

（c）8 > 4，应归入较大数区间，j正常后移，深色区域增加。

（d）7 > 4，应归入较大数区间，j正常后移，深色区域增加。

（e）1 < 4，应归入较小数区间，i进行后移，并与j指向的元素交换，浅色区域增加。

（f）3 < 4，应归入较小数区间，i进行后移，并与j指向的元素交换，浅色区域增加。

（g）5 > 4，应归入较大数区间，j正常后移，深色区域增加。

（h）6 > 4，应归入较大数区间，j正常后移，深色区域增加。

（i）此时j已达到边界，最后只需要将**深色区域的首个元素（8）与待排元素（4）**交换。

注：有关于子序列的划分方式有多种实现方法，如还可以采用从两端不断同时向中间靠近的方式，大家可以自行实现。

3. 伪代码

在快速排序中使用到了递归的操作，在编写伪代码时可以使用FUNCTION来声明定义一个函数名称，以进行调用：

FUNCTION PARTITION(A,p,r)
x =  A[r]
i = p - 1
for j = p to r - 1
    if a[j] < x
        i = i + 1
        exchange A[i] with A[j]
exchange A[i + 1] with A[r]
return i + 1

PARTITION函数的作用是进行第一趟排序，排好一个元素，并得到两个子序列，返回值就是接下来划分子序列的参照。

FUNCTION QUICKSORT(A,p,r)
if p < r
    q = PARTITION(A,p,r)
    QUICKSORT(A,p,q-1)
    QUICKSORT(A,q+1,r)

QUICKSORT函数中进行了递归的操作，将原问题分解为一系列的子问题，每次都在序列上进行划分、调用的操作，每次不断的改变区间的长度，直到不需要再划分为止。

三、算法实践

1. 算法实现

输入数据（input）：2，8，7，1，3，5，6，4

Java源代码

public class QuickSort {
    public static void main(String[] args) {
        // input data
        int[] a = {2,8,7,1,3,5,6,4};
        // 调用快速排序，传入初始的左右端点
        quickSort(a,0,a.length - 1);
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }
    private static int partition(int[] a,int p,int r){
        // 声明待排元素
        int x = a[r];
        // 初始化较小数区间端点
        int i = p - 1;
        // 循环结束后，区间已经划定完毕
        for(int j = p;j < r;j++){
            // 将较小的数向前扔
            if(a[j] < x){
                i++;
                // 交换两个元素
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
        // 交换待排元素到指定位置
        int tmp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = tmp;
        return i + 1;
    }
    private static void quickSort(int[] a,int p,int r){
        // 重要：递归的出口（终止条件）为区间长度小于1
        if(p < r){
            // 划分后得到已排好元素的位置
            int q = partition(a,p,r);
            // 根据位置得到较小数列区间
            quickSort(a,p,q-1);
            // 根据位置得到较大数序列区间
            quickSort(a,q + 1,r);
        }
    }
}

推荐大家使用debug的方式来具体查看一下算法的整个执行过程。

执行效果

2. 时间复杂度

对于快速排序有个小小不确定的因素就是每次待排元素的选择，其实并不是固定的，但是由于序列也是随机的，所以我们可以忽略这个小问题。

对于快速排序来说，由于无论如何划分，比较的次数都是固定的，不会超过O(n) ，那么划分的次数就尤为重要了，这也是重点分析的方面。

最坏的情况

如果初始序列已经有序时，可以试想一下，每次排好一个元素，并且都要挨个比较一次。重点是划分得到的子序列只有一个，如果按照上文，每次选取区间右端点作为待排元素，那么每次只会得到一个较小子序列，在这个序列中再次重复划分的步骤，同样只能得到一个较小子序列，这种情况其实就和冒泡排序的过程很相似了，都是每次只排好一个元素，对其他元素都要比较一遍，此时的时间复杂度为O( n 2 n^{2} n2) 。

最好的情况

由于算法是不断在子序列上递归执行的，如果说每次待排元素都恰好处在中间位置，将原有序列分成两个等长的子序列，每次划分都是这样的情况，那么总共的划分次数就可以用O( l o g 2 n log _{2} n log2n)表示，这样时间复杂度可以在O( n log ⁡ 2 n n\log _{2} n nlog2n) 。

平均情况

对于快速排序来说，是基于关键字比较的内部排序算法中速度最快的，平均性能可以达到O( n log ⁡ 2 n n\log _{2} n nlog2n) 。

3. 空间复杂度

由于使用到了递归操作，所以在执行过程中需要在栈中保存相关信息，需要的空间就和递归次数直接相关。可以知道，在平均情况下，需要O( l o g 2 n log _{2} n log2n) ，在最坏的情况下，不会超过O(n) 。

文章来自；1