快速排序算法详解

快速排序算法详解

引用

CSDN

1.

https://blog.csdn.net/iqanchao/article/details/145961897

快速排序是一种非常高效的排序算法，采用分治策略对数组进行排序。本文将详细介绍快速排序的算法原理、代码实现（C++和Python）、时间复杂度和空间复杂度分析，帮助读者全面理解这一经典算法。

算法原理

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

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

时间复杂度分析

快速排序的时间复杂度分析，利用二叉树来分析快速排序的时间复杂度更容易理解。
结合前面的算法实现，可以发现如下的规律：

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

最佳时间复杂度

最佳的时间复杂度问题变成了，每次分区都将数组分成平均相等的两份，请看下面的图片：

由图可知二叉树的每一层的节点的和为n，那么要求所有二叉树节点的和需要知道树的高度：
树的高度：h = logn
因为每一层都是上一层数值的1/2。
现在知道了树的高度，那么最佳的时间复杂度为：
**最佳时间复杂度 = h * n=O(nlogn) **

最差时间复杂度

最差的时间复杂度就需要求解二叉树如何分布，可以使得所有节点的和最大。那只有数组分区时极度不平衡，那么每次数据在一边。如下图所示：

这是时候变成了：最差时间复杂度 = n + (n-1) + (n-2) + ...+1=(n+1)*n/2=O(n^2)

空间复杂度分析

最佳空间复杂度

递归函数的空间复杂度一般将函数栈作为一个空间单位，因为一个函数栈包含了临时变量、参数等。占用函数栈个数最少的二叉树分布就是最佳空间复杂度。那么怎么理解空间复杂度最低呢？答案是使的二叉树的高度最低，那么数组每次如何分布才能最低呢？那只有二叉平衡树高度最低了。即每次数组分区按照平均分配的方法进行分区。
最佳空间复杂度 = 最短的树的高度 = O(logn)

最差时间复杂度

同理，最差的时间复杂度肯定递归调用同时占据最多个函数栈空间的就是最差空间复杂度。
最差空间复杂度 = 最大的二叉树高度 = O(n)

平均时间/空间复杂度

通过前面的章节知道了存在最佳时间复杂度和最差时间复杂度，但是有另外一个概念叫做平均时间复杂度，那这个平均时间复杂度应该如何评估呢？我从一本书里得到了这样的答案：
平均时间复杂度 = 最佳时间复杂度
最佳情况就是平均情况，以快速排序算法为例，只要你随机的选择一个数值为基准值进行排序，那么得到的时间就是最佳时间复杂度。
平均空间复杂度同理：平均空间复杂度 = 最佳空间复杂度

快速排序算法是最快的排序算法之一。