7.快速排序

算法 > 排序算法 算法 排序算法
发布时间 :
字数:5k 阅读 : 评论:
  1. 7.快速排序
    1. 7.1 基础知识
      1. 核心思想
      2. 算法步骤
      3. 时间复杂度
      4. 空间复杂度
      5. 稳定性
      6. 适用场景
      7. 代码步骤
      8. 总结说明
    2. 快速排序是一种高效的排序算法，尤其在平均情况下具有较低的时间复杂度。然而，需要注意其不稳定性和最坏情况下可能出现的性能问题。在处理大规模数据集时，快速排序是一个强大的选择，尤其适用于内存受限的情况。
    3. 7.2 思路框架
    4. 7.3 纯净代码
    5. 7.4 带注释代码
    6. 7.5 运行结果

7.快速排序

7.1 基础知识

核心思想

快速排序采用分治法，通过选择一个基准元素，将数组分为两个子数组，一个子数组的元素都小于基准，另一个子数组的元素都大于基准，然后递归地对子数组进行排序。每轮选出一个”基准”元素，将比它小的元素放在左边，比它大的元素放在右边，以此达到排序的目的。

算法步骤

  • 选择基准：从数组中选择一个元素作为基准。
  • 分区：将数组中小于基准的元素移到基准的左边，大于基准的元素移到基准的右边。
  • 递归排序：对基准左右两侧的子数组递归地应用快速排序。
  • 合并（可忽略，因为快速排序是原地排序）：由于每一步都将元素放置在其最终位置，不需要显式的合并操作。

时间复杂度

快速排序的平均时间复杂度为 O(n log n)，最坏情况下为 O(n^2)（发生在每次选择的基准都是最大或最小元素的情况），但通过随机选择基准和优化算法，可以减少最坏情况的发生概率。

空间复杂度

快速排序是原地排序算法，其空间复杂度为 O(log n)，主要消耗的是递归调用的栈空间。

稳定性

快速排序通常是不稳定的，因为在分区过程中，相同元素的相对顺序可能被改变。

适用场景

快速排序适用于大规模数据集的排序，尤其在需要原地排序时。由于其平均时间复杂度较低，通常比归并排序更快。

代码步骤

  1. QuickSort 函数：接收一个数组进行快速排序。调用 QuickSortRecursive 函数传入数组和数组的起始终止索引，作为递归入口。
  2. QuickSortRecursive 函数：接收数组和数组的起始终止索引。如果起始索引小于终止索引说明有元素要排序。调用 Partition 函数得到基准索引，分区递归调用 QuickSortRecursive 函数排序左右子数组。
  3. 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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏