当前位置： 首页 > article >正文

排序算法 -快速排序

article 2024/11/18 22:32:30

文章目录

  • 1. 快速排序（Quick Sort）
    • 1.1、 简介
    • 1.2、 快速排序的步骤
  • 2. Hoare 版本
    • 2.1、 基本思路
        • 1. 分区（Partition）
        • 2. 基准选择（Pivot Selection）
        • 3. 递归排序（Recursive Sorting）
    • 2.2 、代码实现
    • 2.3、 代码解释
      • 1. `GetMid` 函数：三数取中
        • 作用：
        • 逻辑：
      • 2. `HoreQuickSort` 函数：Hoare 分区法的快速排序
        • 主要步骤：
        • 代码整体总结
    • 2.4 、动画展示
  • 3. 挖坑版
    • 3.1、基本思路
    • 3.2、挖坑法步骤
    • 3.3、代码实现
    • 3.4、动画展示
  • 4. 前后指针
    • 4.1、基本思路
    • 4. 2、步骤
    • 4.3 、代码中的实现：
      • 解释：
    • 4. 4 、动画展示

1. 快速排序（Quick Sort）

1.1、 简介

快速排序（Quick Sort）是一种高效的排序算法，通常用于大数据集的排序。它由英国计算机科学家 Tony Hoare 在 1960 年提出，并基于分治法（Divide and Conquer）的思想来排序数组或列表。

1.2、 快速排序的步骤

  1. 选择基准（Pivot）：

    • 从数组中选择一个元素作为基准。基准的选择方法会影响算法的性能，常用的基准选择策略包括：
      • 选择第一个元素
      • 选择最后一个元素
      • 选择中间元素
      • 随机选择
      • 三数取中法（选择第一个、最后一个和中间位置的元素中位数作为基准）

  2. 划分（Partition）：

    • 将数组分为两部分，使得：
      • 一部分的元素都小于等于基准；
      • 另一部分的元素都大于基准。
    • 此时，基准元素已经在排序后的正确位置上。

  3. 递归排序：

    • 对基准左侧的子数组和右侧的子数组递归地进行快速排序。
    • 当子数组长度为 1 或 0 时，递归结束，此时该部分已经有序。

2. Hoare 版本

2.1、 基本思路

这个代码的基本思路是实现快速排序（QuickSort）算法的一个优化版本，主要包含 分区、递归 和 基准选择 三个关键步骤。以下是简化后的基本思路：

1. 分区（Partition）

快速排序的核心是“分区”操作。它通过选择一个基准值，将数组分成左右两部分，使得左侧的元素都小于等于基准，右侧的元素都大于等于基准。完成分区后，基准元素会处于它排序后的最终位置。

2. 基准选择（Pivot Selection）

在分区过程中，基准的选择直接影响算法的效率。理想情况下，基准会将数组分成大小相近的两部分，避免极端情况的出现。这里使用 三数取中法 来选择基准，即取数组左端、中间、右端的三个值中间的那个作为基准值。这样能够减少最坏情况的出现（例如数组本身有序时的情况），提高算法的平均性能。

3. 递归排序（Recursive Sorting）

完成分区后，基准两侧的子数组还未有序，需要对每个子数组继续进行快速排序。通过递归调用，将每个子数组逐步分成更小的部分，最终达到完全有序。递归的终止条件是数组长度为 1 或 0，这种情况直接返回，无需再排序。

2.2 、代码实现

#include <stdio.h>

// 交换函数
void Swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 三数取中函数，返回左、中、右三者的中间值索引
int GetMid(int *a, int left, int right) {
    int mid = left + (right - left) / 2;
    if (a[left] > a[right]) {
        Swap(&a[left], &a[right]);
    }
    if (a[mid] > a[right]) {
        Swap(&a[mid], &a[right]);
    }
    if (a[left] < a[mid]) {
        Swap(&a[left], &a[mid]);
    }
    return left;  // 返回基准元素的索引
}

// Hoare 分区法的快速排序
void HoreQuickSort(int *a, int left, int right) {
    if (left >= right) {
        return;
    }

    int begin = left, end = right;
    int key = GetMid(a, left, right);  // 三数取中并将基准值放到left位置
    Swap(&a[left], &a[key]);           // 将基准交换到左端作为参考

    while (begin < end) {
        // 从右往左找到第一个小于基准的元素
        while (begin < end && a[end] >= a[left]) {
            --end;
        }
        // 从左往右找到第一个大于基准的元素
        while (begin < end && a[begin] <= a[left]) {
            ++begin;
        }
        // 交换左右不符合顺序的元素
        if (begin < end) {
            Swap(&a[begin], &a[end]);
        }
    }

    // 最后将基准元素放到分区点
    Swap(&a[left], &a[begin]);

    // 递归排序左右两部分
    HoreQuickSort(a, left, begin - 1);
    HoreQuickSort(a, begin + 1, right);
}

// 打印数组
void print_array(int *a, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    print_array(arr, n);

    HoreQuickSort(arr, 0, n - 1);

    printf("排序后数组: ");
    print_array(arr, n);

    return 0;
}

2.3、 代码解释

1. GetMid 函数：三数取中

int GetMid(int *a, int left, int right) {
    int mid = left + (right - left) / 2; // 计算中间索引
    if (a[left] > a[right]) {
        Swap(&a[left], &a[right]); // 保证a[left] <= a[right]
    }
    if (a[mid] > a[right]) {
        Swap(&a[mid], &a[right]);   // 保证a[mid] <= a[right]
    }
    if (a[left] < a[mid]) {
        Swap(&a[left], &a[mid]);    // 保证a[left] <= a[mid]
    }
    return left; // 返回左索引位置作为基准索引
}
作用：

GetMid 函数的目的是在 左端、中间、右端 三个元素中选出中间值作为基准，避免在近乎有序的数组中使用一个极值作为基准，从而减少分区的不平衡问题。

逻辑：
  • a[left] > a[right] 时交换，确保 a[left] 比 a[right] 小。
  • a[mid] > a[right] 时交换，确保 a[mid] 也比 a[right] 小。
  • a[left] < a[mid] 时交换，这样 a[left] 成为了中间值。
  • 最后返回 left，将三数取中的结果放到 a[left]，作为基准值。

2. HoreQuickSort 函数：Hoare 分区法的快速排序

void HoreQuickSort(int *a, int left, int right) {
    if (left >= right) {
        return;  // 基本情况：如果只有一个元素或无元素，直接返回
    }

    int begin = left, end = right; // 初始化分区指针
    int key = GetMid(a, left, right);  // 选择基准并取三数中值
    Swap(&a[left], &a[key]);           // 将基准交换到左端

    while (begin < end) {
        // 从右向左找到第一个小于基准的元素
        while (begin < end && a[end] >= a[left]) {
            --end;
        }
        // 从左向右找到第一个大于基准的元素
        while (begin < end && a[begin] <= a[left]) {
            ++begin;
        }
        // 交换找到的元素
        if (begin < end) {
            Swap(&a[begin], &a[end]);
        }
    }

    // 最后将基准元素放到最终位置
    Swap(&a[left], &a[begin]);

    // 递归排序左右两部分
    HoreQuickSort(a, left, begin - 1);
    HoreQuickSort(a, begin + 1, right);
}
主要步骤：

  1. 基准选择与初始化：

    • 使用 GetMid 进行三数取中法选择基准，减少最坏情况下的不平衡。
    • 将基准交换到 left 位置，方便分区操作。

  2. 分区过程：

    • begin 和 end 分别从左、右两端向中间移动。
    • 从右向左找到第一个小于基准的元素，将 end 移动到该位置。
    • 从左向右找到第一个大于基准的元素，将 begin 移动到该位置。
    • 如果 begin < end，交换 a[begin] 和 a[end]，确保小于基准的值在左侧，大于基准的值在右侧。
    • 循环直到 begin >= end，此时 begin 指向的元素是分区的正确位置。

  3. 基准位置调整：

    • 将 a[left]（即基准值）和 a[begin] 交换，使基准值放置在分区中间的正确位置。

  4. 递归调用：

    • 对基准左侧（left 到 begin - 1）和右侧（begin + 1 到 right）的子数组分别递归调用 HoreQuickSort 进行排序，直到整个数组有序。
代码整体总结
  • Hoare 分区法：通过双指针从两端向中间扫描，交换不符合条件的元素，提高分区效率。
  • 三数取中法：选基准时用三数取中法，减少极端情况的出现。
  • 递归快速排序：分区后对左右两部分递归排序，直到每个子数组有序。

2.4 、动画展示

hore

3. 挖坑版

快速排序挖坑法是一种直观且高效的排序算法实现方式，它基于分治策略，通过递归地将数组分成较小的子数组来排序。以下是关于快速排序挖坑法的详细解释：

3.1、基本思路

快速排序的基本思想是选择一个基准值（pivot），然后将数组分成两部分：一部分包含所有小于基准值的元素，另一部分包含所有大于基准值的元素。接着，递归地对这两部分进行同样的操作，直到整个数组有序。

3.2、挖坑法步骤

  1. 选择基准值：

    • 通常选择数组的第一个元素、最后一个元素或中间元素作为基准值。为了简单起见，这里以第一个元素为例。
    • 记住基准值的位置，这个位置相当于一个“坑”。

  2. 初始化指针：

    • 设置两个指针，left和right，分别指向数组的最左和最右两个元素。

  3. 从右向左遍历：

    • 从right指针开始，将指针所指向的元素与基准值进行比较。
    • 如果元素大于基准值，则right指针向左移动。
    • 如果元素小于基准值，则将该元素填入坑中（即基准值原本的位置），并将该元素原本的位置视为新的坑。同时，left指针向右移动一位。

  4. 从左向右遍历：

    • 从left指针开始，将指针所指向的元素与基准值进行比较（注意，此时基准值已被某个元素替换，因此实际上是与该元素进行比较）。
    • 如果元素小于基准值（实际上是小于刚才被填入坑中的那个元素，因为基准值已被替换），则left指针向右移动。
    • 如果元素大于基准值，则将该元素填入坑中，并将该元素原本的位置视为新的坑。同时，right指针向左移动一位。

  5. 重复步骤3和4：

    • 继续按照上述步骤进行遍历，直到left和right指针重合。

  6. 放入基准值：

    • 当left和right指针重合时，将基准值（或最初被选出的那个基准值的值，如果它在遍历过程中被替换了的话）放入重合的位置。
    • 此时，基准值左边的所有元素都小于它，右边的所有元素都大于它。

  7. 递归排序：

    • 对基准值左边和右边的子数组递归地进行上述操作，直到整个数组有序。

3.3、代码实现

// 挖坑法快速排序
void HoleQuickSort(int* arr, int left, int right)
{
    if (left >= right)
        return;

    // 使用第一个元素作为基准值（也可以选择其他方式，如三数取中）
    int pivotValue = arr[left];
    int holeIndex = left; // 挖坑的位置，初始化为基准值的位置
    int scanLeft = left, scanRight = right; // 左右扫描指针

    // 从右向左扫描，找到第一个小于基准值的元素
    while (scanRight > scanLeft)
    {
        // 从右向左找到第一个小于基准值的元素
        while (scanRight > scanLeft && arr[scanRight] >= pivotValue)
            scanRight--;

        // 如果找到，将该元素放到坑里（holeIndex位置）
        if (scanRight > scanLeft)
        {
            arr[holeIndex] = arr[scanRight];
            holeIndex = scanRight; // 更新坑的位置到当前元素的位置
        }

        // 从左向右扫描，找到第一个大于基准值的元素
        while (scanRight > scanLeft && arr[scanLeft] <= pivotValue)
            scanLeft++;

        // 如果找到，将该元素放到坑里（此时坑的位置可能已经被更新）
        if (scanRight > scanLeft)
        {
            arr[holeIndex] = arr[scanLeft];
            holeIndex = scanLeft; // 再次更新坑的位置
        }
    }

    // 当左右扫描指针相遇时，将基准值放到坑里
    arr[holeIndex] = pivotValue;

    // 递归排序基准值左右两侧的子数组
    HoleQuickSort(arr, left, holeIndex - 1);
    HoleQuickSort(arr, holeIndex + 1, right);
}

// 辅助函数：交换两个整数的值（此函数在您的原始代码中已提供，但为完整性而保留）
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

3.4、动画展示

w

4. 前后指针

4.1、基本思路

快速排序的前后指针法（也叫“双指针法”）是快速排序中的一种常见分区方法。这个方法通过两个指针，分别从数组的左右两端开始，来逐步划分数组，使得数组中的元素相对于一个基准元素（通常是数组的第一个元素）进行排序。

4. 2、步骤

  1. 选择基准元素：选择数组中的一个元素作为基准（pivot）。在你给出的代码中，基准是数组的第一个元素 key。

  2. 设置两个指针：

    • 前指针（pre）：从左边开始，指向当前已经被正确分区的区域的末尾。初始时，pre 指向基准元素。
    • 后指针（cur）：从左边的第二个元素开始，遍历整个数组，用来扫描比基准小的元素。

  3. 扫描并交换：

    • 前指针会不断向右移动，找到一个比基准小的元素。
    • 后指针会遍历数组，直到找到一个比基准大的元素。
    • 如果后指针找到一个大于基准的元素，同时前指针找到了一个小于基准的元素，则交换这两个元素。这保证了所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。

  4. 完成分区：

    • 当两个指针相遇时，或者后指针扫描到数组的右边界时，前后指针停止。
    • 这时，将基准元素和 pre 指针所指向的元素交换。这样，基准元素就放置在了正确的位置上，左边是比基准小的元素，右边是比基准大的元素。

  5. 递归排序：对基准元素左边和右边的子数组继续使用相同的分区方法递归进行排序，直到子数组的大小为 1 或 0。

4.3 、代码中的实现：

void FbQuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;

    int pre = left;  // 前指针，初始化为 left
    int cur = left + 1;  // 后指针，初始化为 left + 1
    int key = a[left];  // 选择基准元素为 left

    while (cur <= right)
    {
        if (a[cur] < key)  // 如果当前元素小于基准元素
        {
            pre++;  // 前指针右移
            Swap(&a[cur], &a[pre]);  // 交换当前元素与前指针指向的元素
        }
        cur++;  // 后指针继续右移
    }

    // 最后将基准元素与前指针指向的元素交换
    Swap(&a[left], &a[pre]);

    // 递归对左边和右边的子数组进行快速排序
    FbQuickSort(a, left, pre - 1);
    FbQuickSort(a, pre + 1, right);
}

解释：

  1. 基准元素：key = a[left]，我们选择数组的第一个元素作为基准。
  2. 前后指针初始化：pre = left，cur = left + 1。pre 记录当前已经排序好的区域的边界，cur 用来遍历剩余的部分。
  3. 主循环：while (cur <= right) 让后指针 cur 遍历整个数组。在每次扫描中，检查当前元素是否小于基准元素，如果是，则将其与前指针 pre 所指向的元素交换，同时 pre 自增。
  4. 基准交换：Swap(&a[left], &a[pre]) 将基准元素交换到其最终位置，这时 pre 的位置已经确定了基准元素应该放置的位置。左边是比基准小的元素，右边是比基准大的元素。
  5. 递归调用：对基准元素左右两侧的子数组递归进行快速排序。

4. 4 、动画展示

pb


http://www.kler.cn/a/399289.html

相关文章：

  • SQL面试题——抖音SQL面试题 主播播出时长
  • Tomcat启动过程中cmd窗口（控制台）中文乱码的问题
  • RabbitMQ的工作队列在Spring Boot中实现（详解常⽤的⼯作模式）
  • ＜项目代码＞YOLOv8 番茄识别＜目标检测＞
  • 深度学习神经网络创新点方向
  • 工厂模式-工厂方法模式实现
  • 【 LLM论文日更｜检索增强：大型语言模型是强大的零样本检索器 】
  • Java基础-组件及事件处理（中）
  • 深度学习的艺术：揭秘卷积神经网络（CNN）的神秘面纱
  • Linux-何为CentOS
  • Unity3D中管理Shader效果详解
  • 算法定制LiteAIServer摄像机实时接入分析平台玩手机打电话检测算法：智能监控的新篇章
  • 基础：用卷积神经网络（CNN）进行猫狗图像分类
  • （四）P2Link内置HTTP服务，分享本地文件
  • 力扣515：在每个树行中找最大值
  • 云原生周刊：Istio 1.24.0 正式发布
  • css:盒子模型
  • 【GAT】 代码详解 (1) 运行方法【pytorch】可运行版本
  • React Native 全栈开发实战班 -原生功能集成之相机与图片
  • 希尔排序（C语言）
  • 基于STM32设计的大棚育苗管理系统(4G+华为云IOT)_265
  • 易考八股文之Elasticsearch合集
  • 微信小程序自定义顶部导航栏（适配各种机型）
  • IOException: Broken pipe与IOException: 远程主机强迫关闭了一个现有的连接
  • C语言项⽬实践-贪吃蛇
  • Asp.net Mvc 电脑销售系统