7.快速排序
7.1 基础知识
核心思想
快速排序采用分治法，通过选择一个基准元素，将数组分为两个子数组，一个子数组的元素都小于基准，另一个子数组的元素都大于基准，然后递归地对子数组进行排序。每轮选出一个”基准”元素，将比它小的元素放在左边，比它大的元素放在右边，以此达到排序的目的。
算法步骤
- 选择基准：从数组中选择一个元素作为基准。
- 分区：将数组中小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。
- 递归排序：对基准左右两侧的子数组递归地应用快速排序。
- 合并（可忽略，因为快速排序是原地排序）：由于每一步都将元素放置在其最终位置，不需要显式的合并操作。
时间复杂度
快速排序的平均时间复杂度为 O(n log n)，最坏情况下为 O(n^2)（发生在每次选择的基准都是最大或最小元素的情况），但通过随机选择基准和优化算法，可以减少最坏情况的发生概率。
空间复杂度
快速排序是原地排序算法，其空间复杂度为 O(log n)，主要消耗的是递归调用的栈空间。
稳定性
快速排序通常是不稳定的，因为在分区过程中，相同元素的相对顺序可能被改变。
适用场景
快速排序适用于大规模数据集的排序，尤其在需要原地排序时。由于其平均时间复杂度较低，通常比归并排序更快。
代码步骤
- QuickSort 函数：接收一个数组进行快速排序。调用 QuickSortRecursive 函数传入数组和数组的起始终止索引，作为递归入口。
- QuickSortRecursive 函数：接收数组和数组的起始终止索引。如果起始索引小于终止索引说明有元素要排序。调用 Partition 函数得到基准索引，分区递归调用 QuickSortRecursive 函数排序左右子数组。
- Partition 函数：接收数组和数组的起始终止索引，实现分区操作并返回基准索引。把终止索引上的元素作为基准。定义小于基准区的元素计数标识。目的要将小于基准的元素移到左边，大于基准的元素移到右边。遍历起始索引到终止索引-1上的元素，如果发现比基准小的元素就扩大小于基准区的元素计数标识，并把当前发现的比基准小的元素和刚扩大的坑的元素进行交换，保证新扩大的坑是小于基准的，可以加入判断优化，当前遍历索引和小于基准区的元素计数标识相同可以不换。遍历完交换终止索引上的元素（即基准元素）和小于基准区的元素计数标识+1的元素。返回小于基准区的元素计数标识+1，因为这是基准索引。
总结说明
快速排序是一种高效的排序算法，尤其在平均情况下具有较低的时间复杂度。然而，需要注意其不稳定性和最坏情况下可能出现的性能问题。在处理大规模数据集时，快速排序是一个强大的选择，尤其适用于内存受限的情况。
7.2 思路框架
static void QuickSort(ref int[] array)
{
调用快速排序递归部分方法QuickSortRecursive，传入数组、左边界和右边界索引
}
static void QuickSortRecursive(int[] array, int left, int right)
{
如果左边界小于右边界
{
调用找基准索引方法Partition找到基准索引
根据基准点对左右两半部分调用快速排序递归部分方法QuickSortRecursive
}
}
目的要将小于基准的元素移到左边，大于基准的元素移到右边。并返回基准所在索引。
static int Partition(int[] array, int left, int right)
{
以数组的最后一个元素作为基准（pivot）
定义一个指针（lessIndex）初始值为左边界 - 1，代表小于基准元素边界位置
遍历数组中的元素（从左边界到右边界-1）
{
如果当前元素小于或等于基准，则将 lessIndex 向右移动一位，并交换 lessIndex 和当前元素的位置，这样保证了每扩展一个小于基准位置的席位，上面的元素也是小于基准的
}
将基准与 lessIndex 后一位的元素交换位置，并返回 lessIndex 后一位的索引作为新的基准位置
}
7.3 纯净代码
static void QuickSort(ref int[] array)
{
QuickSortRecursive(array, 0, array.Length - 1);
}
static void QuickSortRecursive(int[] array, int left, int right)
{
if (left < right)
{
int pivotIndex = Partition(array, left, right);
QuickSortRecursive(array, left, pivotIndex - 1);
QuickSortRecursive(array, pivotIndex + 1, right);
}
}
static int Partition(int[] array, int left, int right)
{
int pivot = array[right];
int lessIndex = left - 1;
for (int i = left; i < right; i++)
{
if (array[i] <= pivot)
{
lessIndex++;
if (lessIndex != i)
{
SortHelpTool.Swap(ref array[lessIndex], ref array[i]);
}
}
}
SortHelpTool.Swap(ref array[lessIndex + 1], ref array[right]);
return lessIndex + 1;
}
require("Lesson01_SortHelpTool")
-- 快速排序函数
function QuickSort(array)
array = QuickSortRecursive(array, 1, #array)
return array
end
function QuickSortRecursive(array, left, right)
if left < right then
local middle = Partition(array, left, right)
QuickSortRecursive(array, left, middle - 1)
QuickSortRecursive(array, middle + 1, right)
end
return array
end
function Partition(array, left, right)
local pivot = array[right]
local lessIndex = left - 1
for i = left, right - 1 do -- 修改了这里，将 1 改为 left
if array[i] <= pivot then -- 修复了此处的比较对象，应为 array[i]
lessIndex = lessIndex + 1
SortHelpTool.Swap(array, lessIndex, i)
end
end
SortHelpTool.Swap(array, lessIndex + 1, right)
return lessIndex + 1
end
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")
SortHelpTool.arrayToSort = QuickSort(SortHelpTool.arrayToSort)
SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")
7.4 带注释代码
using System;
using Lesson01_概述;
class Program
{
static void Main()
{
// 输出排序前的数组
Console.WriteLine("排序前的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
// 调用快速排序函数
QuickSort(ref SortHelpTool.arrayToSort);
// 输出排序后的数组
Console.WriteLine("排序后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
}
// 快速排序函数
static void QuickSort(ref int[] array)
{
// 调用快速排序辅助函数
QuickSortRecursive(array, 0, array.Length - 1, 0);
}
// 快速排序的递归函数
static void QuickSortRecursive(int[] array, int left, int right, int depth)
{
Console.WriteLine(new String('-', 2 * depth) + $"开始快速排序的递归部分函数，深度是{depth}");
// 如果左边索引小于右边索引，说明还有至少两个元素需要排序
if (left < right)
{
// 打印当前递归深度和子数组范围
Console.WriteLine(
new String('-', 2 * depth) + $"左边索引小于右边索引，至少有两个元素需要排序，左边索引是{left}，右边索引是{right}，深度是{depth}");
Console.WriteLine(new String('-', 2 * depth) + $"开始获取基准元素的索引，深度是{depth}");
// 获取基准元素的索引
int pivotIndex = Partition(array, left, right, depth);
// 打印当前递归深度
Console.WriteLine(new String('-', 2 * depth) + $"结束获取基准元素的索引，基准元素的索引是{pivotIndex}，深度是{depth}");
// 递归对基准左右两侧的子数组进行排序
Console.WriteLine(new String('-', 2 * depth) +
$"开始递归对基准左侧的子数组进行排序，左半部分开始索引是{left}，终止索引是{pivotIndex - 1}，深度是{depth}");
QuickSortRecursive(array, left, pivotIndex - 1, depth + 1);
Console.WriteLine(new String('-', 2 * depth) +
$"结束递归对基准左侧的子数组进行排序，左半部分开始索引是{left}，终止索引是{pivotIndex - 1}，深度是{depth}");
Console.WriteLine(new String('-', 2 * depth) +
$"开始递归对基准右侧的子数组进行排序，右半部分开始索引是{pivotIndex + 1}，终止索引是{right}，深度是{depth}");
QuickSortRecursive(array, pivotIndex + 1, right, depth + 1);
Console.WriteLine(new String('-', 2 * depth) +
$"结束递归对基准右侧的子数组进行排序，右半部分开始索引是{pivotIndex + 1}，终止索引是{right}，深度是{depth}");
}
Console.WriteLine(new String('-', 2 * depth) + $"结束快速排序的递归部分函数，深度是{depth}");
}
// 快速排序的分区函数
// 选择最右边的元素作为基准 目的是让基准左边的数都小于基准 基准右边的数都大于基准 返回基准的索引 方便下次递归
static int Partition(int[] array, int left, int right, int depth)
{
// 选择基准元素，这里选择最右边的元素作为基准
int pivot = array[right];
// 初始化小于等于基准元素的子数组的右边界 可以理解为记录比基准元素小的元素有多少个 最后判断基准元素的位置
int lessIndex = left - 1;
// 遍历数组元素，将小于等于基准元素的元素交换到左侧
// 当发现比基准大的元素时 lessIndex不会扩大 但是i会继续+
// i继续+的时候找到比基准小的元素 就扩大小于等于基准元素区的范围 让新扩大的坑的元素和刚刚找的比基准小的元素交换
for (int i = left; i < right; i++)
{
// 如果当前元素小于等于基准
if (array[i] <= pivot)
{
// 移动小于等于基准元素的子数组的右边界 因为又多了一个比基准小的元素 相当于扩大小于等于基准元素区的范围
lessIndex++;
if (lessIndex != i)
{
// 交换当前元素 就是要把当前发现比基准小的元素放到新扩大的比基准小的坑上
Console.WriteLine(new String('-', 2 * depth) +
$"深度是{depth} 交换 索引为{lessIndex}的元素{array[lessIndex]} 和 索引为{i}的元素{array[i]}");
SortHelpTool.Swap(ref array[lessIndex], ref array[i]);
// 打印每次交换后的数组状态
Console.Write(new String('-', 2 * depth) + $"深度是{depth} 交换元素位置后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
}
}
}
// 将基准元素放到正确的位置 就是小于等于基准元素区索引+1
SortHelpTool.Swap(ref array[lessIndex + 1], ref array[right]);
// 打印将基准元素放到正确位置后的数组状态
Console.Write(new String('-', 2 * depth) + $"深度是{depth} 将基准元素放到正确的位置后的数组:");
SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
// 返回小于等于基准元素的子数组的右边界，即最终放置基准元素的位置
return lessIndex + 1;
}
}
7.5 运行结果
排序前的数组:
5 2 8 1 7 3 10 4 6 9
开始快速排序的递归部分函数，深度是0
左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是9，深度是0
开始获取基准元素的索引，深度是0
深度是0 交换 索引为6的元素10 和 索引为7的元素4
深度是0 交换元素位置后的数组:5 2 8 1 7 3 4 10 6 9
深度是0 交换 索引为7的元素10 和 索引为8的元素6
深度是0 交换元素位置后的数组:5 2 8 1 7 3 4 6 10 9
深度是0 将基准元素放到正确的位置后的数组:5 2 8 1 7 3 4 6 9 10
结束获取基准元素的索引，基准元素的索引是8，深度是0
开始递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是7，深度是0
–开始快速排序的递归部分函数，深度是1
–左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是7，深度是1
–开始获取基准元素的索引，深度是1
–深度是1 交换 索引为2的元素8 和 索引为3的元素1
–深度是1 交换元素位置后的数组:5 2 1 8 7 3 4 6 9 10
–深度是1 交换 索引为3的元素8 和 索引为5的元素3
–深度是1 交换元素位置后的数组:5 2 1 3 7 8 4 6 9 10
–深度是1 交换 索引为4的元素7 和 索引为6的元素4
–深度是1 交换元素位置后的数组:5 2 1 3 4 8 7 6 9 10
–深度是1 将基准元素放到正确的位置后的数组:5 2 1 3 4 6 7 8 9 10
–结束获取基准元素的索引，基准元素的索引是5，深度是1
–开始递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是4，深度是1
—-开始快速排序的递归部分函数，深度是2
—-左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是4，深度是2
—-开始获取基准元素的索引，深度是2
—-深度是2 交换 索引为0的元素5 和 索引为1的元素2
—-深度是2 交换元素位置后的数组:2 5 1 3 4 6 7 8 9 10
—-深度是2 交换 索引为1的元素5 和 索引为2的元素1
—-深度是2 交换元素位置后的数组:2 1 5 3 4 6 7 8 9 10
—-深度是2 交换 索引为2的元素5 和 索引为3的元素3
—-深度是2 交换元素位置后的数组:2 1 3 5 4 6 7 8 9 10
—-深度是2 将基准元素放到正确的位置后的数组:2 1 3 4 5 6 7 8 9 10
—-结束获取基准元素的索引，基准元素的索引是3，深度是2
—-开始递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是2，深度是2
——开始快速排序的递归部分函数，深度是3
——左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是2，深度是3
——开始获取基准元素的索引，深度是3
——深度是3 将基准元素放到正确的位置后的数组:2 1 3 4 5 6 7 8 9 10
——结束获取基准元素的索引，基准元素的索引是2，深度是3
——开始递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是1，深度是3
——–开始快速排序的递归部分函数，深度是4
——–左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是1，深度是4
——–开始获取基准元素的索引，深度是4
——–深度是4 将基准元素放到正确的位置后的数组:1 2 3 4 5 6 7 8 9 10
——–结束获取基准元素的索引，基准元素的索引是0，深度是4
——–开始递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是-1，深度是4
———-开始快速排序的递归部分函数，深度是5
———-结束快速排序的递归部分函数，深度是5
——–结束递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是-1，深度是4
——–开始递归对基准右侧的子数组进行排序，右半部分开始索引是1，终止索引是1，深度是4
———-开始快速排序的递归部分函数，深度是5
———-结束快速排序的递归部分函数，深度是5
——–结束递归对基准右侧的子数组进行排序，右半部分开始索引是1，终止索引是1，深度是4
——–结束快速排序的递归部分函数，深度是4
——结束递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是1，深度是3
——开始递归对基准右侧的子数组进行排序，右半部分开始索引是3，终止索引是2，深度是3
——–开始快速排序的递归部分函数，深度是4
——–结束快速排序的递归部分函数，深度是4
——结束递归对基准右侧的子数组进行排序，右半部分开始索引是3，终止索引是2，深度是3
——结束快速排序的递归部分函数，深度是3
—-结束递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是2，深度是2
—-开始递归对基准右侧的子数组进行排序，右半部分开始索引是4，终止索引是4，深度是2
——开始快速排序的递归部分函数，深度是3
——结束快速排序的递归部分函数，深度是3
—-结束递归对基准右侧的子数组进行排序，右半部分开始索引是4，终止索引是4，深度是2
—-结束快速排序的递归部分函数，深度是2
–结束递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是4，深度是1
–开始递归对基准右侧的子数组进行排序，右半部分开始索引是6，终止索引是7，深度是1
—-开始快速排序的递归部分函数，深度是2
—-左边索引小于右边索引，至少有两个元素需要排序，左边索引是6，右边索引是7，深度是2
—-开始获取基准元素的索引，深度是2
—-深度是2 将基准元素放到正确的位置后的数组:1 2 3 4 5 6 7 8 9 10
—-结束获取基准元素的索引，基准元素的索引是7，深度是2
—-开始递归对基准左侧的子数组进行排序，左半部分开始索引是6，终止索引是6，深度是2
——开始快速排序的递归部分函数，深度是3
——结束快速排序的递归部分函数，深度是3
—-结束递归对基准左侧的子数组进行排序，左半部分开始索引是6，终止索引是6，深度是2
—-开始递归对基准右侧的子数组进行排序，右半部分开始索引是8，终止索引是7，深度是2
——开始快速排序的递归部分函数，深度是3
——结束快速排序的递归部分函数，深度是3
—-结束递归对基准右侧的子数组进行排序，右半部分开始索引是8，终止索引是7，深度是2
—-结束快速排序的递归部分函数，深度是2
–结束递归对基准右侧的子数组进行排序，右半部分开始索引是6，终止索引是7，深度是1
–结束快速排序的递归部分函数，深度是1
结束递归对基准左侧的子数组进行排序，左半部分开始索引是0，终止索引是7，深度是0
开始递归对基准右侧的子数组进行排序，右半部分开始索引是9，终止索引是9，深度是0
–开始快速排序的递归部分函数，深度是1
–结束快速排序的递归部分函数，深度是1
结束递归对基准右侧的子数组进行排序，右半部分开始索引是9，终止索引是9，深度是0
结束快速排序的递归部分函数，深度是0
排序后的数组:
1 2 3 4 5 6 7 8 9 10
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
