算法系列之快速排序算法

快速排序概述

• 核心思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
• 快速排序使用了分而治之概念，下面我们先充分理解分而治之

---

分而治之概述（D&C）

• 分而治之是一种著名的递归式问题解决方法，提供了解决问题的思路，而不是单独解决某一种问题的算法。它将问题的实例划分为若干个较小的实例(最好拥有相同的规模)，对这些较小的实例递归求解，然后合并这些解，以得到原始问题的解。
• 许多高效的算法都基于这种技术，虽然有时候它的适应性和效率并不如一些更简单的算法

---

举例理解分而治之

• 假设你是农场主，有一小块土地（面积图如下）

• 你要将这块地均匀地分成方块，且分出的方块要尽可能大。
• 但是很显然，下面的几种分法都不符合要求

• 那么如何将一块地均匀地分成方块，并确保分出的方块是最大的呢？
• 使用分而治之策略！我们知道分而治之算法是递归的。使用分而治之解决问题的过程包括两个步骤
  （1）找到基线条件，并且尽可能简单
  （2）不断将问题分解（缩小规模），直到符合基线条件
• 下面就来使用分而治之找出前述问题的解决方案
• 首先，找出基线条件。最容易处理的基线添加是：一条边的长度是另一条边的整数倍（因为这样就可以拆分 为两个相同大小的正方形）
• 如果一边长25m，另一边长50m，那么可使用的最大方块为 25m×25m。换言之，可以将这块地分成两个这样的方块

• 现在需要找出递归条件，这正是分而治之的用武之地。根据分而治之的概述，每次递归调用都必须缩小问题的规模
• 那么如何缩小前述问题的规模呢？我们首先找出这块地可容纳的最大方块

• 你可以从这块地中划出两个640m × 640m的方块，同时余下一小块地。现在是顿悟时刻：何不对余下的那一小块地使用相同的算法呢？
• 最初要划分的土地尺寸为1680m × 640m，而现在要划分的土地更小，为640m × 400m。适用于这小块地的最大方块，也是适用于整块地的最大方块。换言之，你将均匀划分1680m × 640m土地的问题，简化成了均匀划分640m × 400m土地的问题！
• 对于640m × 400m的土地，可从中划出的最大方块为400m × 400m。这将余下一块更小的土地，其尺寸为400m × 240m

• 你可从这块土地中划出最大的方块，余下一块更小的土地，其尺寸为240 m × 160 m

• 接下来，从这块土地中划出最大的方块，余下一块更小的土地

• 余下的这块土地满足基线条件，因为160是80的整数倍。将这块土地分成两个方块后，将不会余下任何土地！

• 因此，对于最初的那片土地，适用的最大方块为80m × 80m

图文理解快速排序

• 对排序算法来说，最简单的数组什么样呢？就是根本不需要排序的数组

• 因此，基线条件为数组为空或只包含一个元素。在这种情况下，只需原样返回数组（根本就不用排序）
• 我们来看看更长的数组。对包含两个元素的数组进行排序也很容易

• 包含三个元素的数组呢？

• 别忘了，你要使用分而治之，因此需要将数组分解，直到满足基线条件。下面介绍快速排序的工作原理。首先，从数组中选择一个元素，这个元素被称为基准值
• 我们暂时将数组的第一个元素用作基准值，也就是 33
• 接下来，找出比基准值小的元素以及比基准值大的元素

• 这被称为分区。现在你有一个由所有小于基准值的数字组成的子数组；基准值；一个由所有大于基准值的数组组成的子数组
• 如何对子数组进行排序呢？只要递归地把小于基准值元素的子数列和大于基准值元素的子数列再次排序，然后合并结果，就能得到一个有序数组

代码理解快速排序

using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 转载请注明唯一出处 - 简书
/// 简书地址：https://www.jianshu.com/u/ab8f5ab027bd
/// 简书作者：SunnyShao
/// 创作时间：2021年9月15号
/// </summary>
public class QuickSortTest : MonoBehaviour
{
    public List<int> startSortlist;

    private void Awake()
    {
        List<int> resultSortList = QuickSortFun(startSortlist);
        for (int i = 0; i < resultSortList.Count; i++)
        {
            Debug.Log(resultSortList[i]);
        }
    }

    private List<int> QuickSortFun(List<int> sortlist)
    {
        if (sortlist.Count < 2)
            return sortlist;                        //基线条件：为空或只包含一个元素的列表是“有序”的

        int datumNum = sortlist[0];                 //获得基准值，也是递归条件
        List<int> endSortlist = new List<int>();
        List<int> lowList = new List<int>();
        List<int> highList = new List<int>();

        for (int i = 1; i < sortlist.Count; i++)
        {
            if (sortlist[i] <= datumNum)
            {
                lowList.Add(sortlist[i]);           //取得所有小于基准值的元素组成的子列表
            }
            else
            {
                highList.Add(sortlist[i]);          //取得所有大于基准值的元素组成的子列表
            }
        }

        //递归计算两个子列表 直到满足基线条件
        lowList = QuickSortFun(lowList);
        highList = QuickSortFun(highList);

        //组合成最新的列表返回
        for (int i = 0; i < lowList.Count; i++)
        {
            endSortlist.Add(lowList[i]);
        }
        endSortlist.Add(datumNum);
        for (int i = 0; i < highList.Count; i++)
        {
            endSortlist.Add(highList[i]);
        }

        return endSortlist;
    }
}

排序前
排序后

快速排序运行速度

• 快速排序的速度有点不同， 最糟情况下运行时间为O(n²），平均情况下为 O(n log n)
• 还有一种名为合并排序的排序算法，其运行时间为O(n log n)，比选择排序O(n²）快得多！
• 若快速排序在平均情况下的运行时间为O(n log n)，而合并排序的运行时间总是O(n log n)，为何不使用合并排序？它不是更快吗？
  其实这和常量有关系，通常大O表示法不考虑常量，因为如果两种算法的大O运行时间不同，这种常量将无关紧要。但有时候，常量的影响可能很大，对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小，因此如果它们的运行时间都为O(n log n)，快速查找的速度将更快。实际上，快速查找的速度确实更快，因为相对于遇上最糟情况，它遇上平均情况的可能性要大得多

---

参考

《算法图解》（确实像小说一样有趣的算法书）