快速排序算法详解

算法原理

快速排序是一种分治的策略的排序算法。它的核心排序思想是将问题不断的分解为子问题。以数组为例进行介绍更容易理解，创建一个数组或者vector，假设是std::vector<int> a{3，2, 1, 5, 4,7}，要对a从小到大进行排序：

首先在a中任意选择一个数值（为了简单起见，这个中间值每次都取数组的第一个数值即可），以这个数值为中间值，通过遍历的方式分别找出小于这个中间值的所有数字放到一个数组或者vector中，这里将包含所有小于中间值数字的数组成为left；同时找出所有大于这个中间值的数字放到一个数组或者vector中，这里将包含所有大于中间值数字的数组成为right。
将数组left作为一个新的整体，重复1的操作，直到数组的长度小于等于1截止，停止重复。
第2步完成后，整个left子数组已经是一个有序的数组
将数组right作为一个新的整体，重复1的操作，直到数组的长度小于等于1截止，停止重复。
第4步完成后，整个right子数组已经一个有序的数组
拼接数组，left数组+中间值+right数组

上面的过程有一个隐性的排序，即在步骤1中每次都会都数组根据中间值编译找出所有小于这个中间值的数字和大于中间值的数组，然后再对子数组重复进行同样的操作，直到最后的子数组长度为1的时候，就完成了这个排序，可以这样理解，在每次问题分解过程中都会遍历当前数组根据选择的数值作为临界值进行一次“排序”，这里的“排序”并不是对整个数组进行排序，而是以选择的临界值分别找出小于这个临界值和大于这个临界值的数字，虽然小于或大于这个临界值的部分没有进行排序，但是我们我们可以将他们继续分解，继续在他们中找出一个临界值，重复这个过程，直至数组的大小为1。这样整个数组通过这样的方式实现了排序的需求。

把上面的内容进行归纳总结：

快速排序是一种分治策略（Divide and Conquer）的排序算法：

选择一个基准值（pivot）
将数组分为两部分：小于基准值的部分和大于基准值的部分
递归地对这两部分进行排序

代码实例

c++实现

//快速排序算法，输入是一个数组，输出也是一个数组
//函数设计，参数为一个vector,无返回值，参数既是输出也是输出,第二个参数表示这个vector的索引
//第三个参数是vector的右索引
/*
 *测试用例：
 *1.只有一个元素
 *2.包含2个元素
 *3.包含多个元素，元素按从小到大顺序排列
 *4.包含多个元素元素从大小顺序排列
 *5.包含多个元素，顺序无序
 *6.包含多个元素，元素都相同
 *
 *
 */
void MyQsort(std::vector<int>& vector)
{
    //如果只有一个元素，无需进行排序，这是基线条件
    if(vector.size() <=1 )
        return;

    int value = vector[0];
    std::vector<int> leftVec;  //用于存储左侧比value小的数值
    std::vector<int> rightVec;  //用于存储右侧比value大的数值
    for(int i = 1; i < vector.size(); i++)
    {
        if(vector[i] >= value)
            rightVec.push_back(vector[i]);
        else
            leftVec.push_back(vector[i]);
    }

    MyQsort(leftVec);  //比该数值小的进行快速排序，成为分解为子问题
    MyQsort(rightVec);  //比该数值大的进行快速排序，成为分解为子问题

    vector.clear();
    vector.insert(vector.begin(), leftVec.begin(), leftVec.end());
    vector.push_back(value);
    vector.insert(vector.end(), rightVec.begin(), rightVec.end());
    return;
}

python实现

import os

def my_qsort(lst):
  length = len(lst)
  if length <= 1:
    return lst
  value = lst[0]
  leftLst = [x for x in lst[1:] if x < value]
  rightLst = [x for x in lst[1:] if x >= value]

  leftLst = my_qsort(leftLst)
  rightLst = my_qsort(rightLst)
  lst = leftLst+[value]+rightLst
  print(f'--lst={lst}')
  return lst

lst = [5,2,3,8,1,7]
lst = my_qsort(lst)
print(f'lst={lst}')

#输出
--lst=[1, 2, 3]
--lst=[7, 8]
--lst=[1, 2, 3, 5, 7, 8]
lst=[1, 2, 3, 5, 7, 8]

时间复杂度分析

快速排序的时间复杂度分析，利用二叉树来分析快速排序的时间复杂度更容易理解。

结合前面的算法实现，可以发现如下的规律：

假设待排序的数组中有个n个数值，递归的第一层作为二叉树的根节点，再这一层中有一个for循环遍历了n次，所以设这个节点的值为n；同时递归的首层分出了两个子数组，将这两个子树作为根节点的两个子节点，并且这两个字子节点的和是n
两个子节点每个都做一个新的二叉树的根节点，然后继续生成的新的子节点，但是有一个规律即两个子节点的和都等于根节点的值。
由此可以得出一个结论二叉树每一层的和都是n
要求这棵二叉树中所有节点值的和就是时间复杂度

这个问题就转变成了一棵二叉树问题，现在求解二叉树的最好时间复杂度变成了如何求解二叉树如何分布时间复杂度最低；求解最差时间复杂度变成了求解二叉树如何分布时间复杂度最高。