【CS.AL】八大排序算法 —— 快速排序全揭秘:从基础到优化

2024-06-09 11:04

本文主要是介绍【CS.AL】八大排序算法 —— 快速排序全揭秘:从基础到优化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

文章目录

    • 1. 快速排序简介
      • 1.1 定义
      • 1.2 时间复杂度
      • 1.3 相关资源
    • 2. 最优的Partition算法 🔥
      • 2.1 Introsort简介
      • 2.2 过程示例
    • 3. 非递归快速排序
      • 3.1 实现
    • 4. 递归快速排序
      • 4.1 实现
    • 5. 有问题的Partition
      • 5.1 实现
    • 6. 三中位数主元选择
      • 6.1 实现
    • 7. 总结

1. 快速排序简介

1.1 定义

快速排序:快速排序也采用分治策略,选择一个基准元素,将数组分成比基准小和比基准大的两部分,再对两部分递归地进行排序。快速排序的平均时间复杂度为O(n log n),是目前应用广泛的排序算法之一。

1.2 时间复杂度

  • 最坏情况:O(n²)
  • 平均情况:O(n log₂n)
  • 最佳情况:O(n log₂n)

1.3 相关资源

912. 排序数组 - 力扣(LeetCode)

2. 最优的Partition算法 🔥

2.1 Introsort简介

Introsort(内排序)从快速排序开始作为主要排序算法。在最坏情况下(例如,数组已经排序或接近排序),快速排序可能退化为O(n²)时间复杂度。为了避免快速排序的最坏情况,Introsort引入了一个最大递归深度。当递归深度超过这个阈值时,算法切换到堆排序或归并排序,以确保更好的最坏情况性能。

template <typename Tp>
int partition(vector<Tp>& nums, int lIdx, int rIdx) {int randomIndex = lIdx + rand() % (rIdx - lIdx + 1);std::swap(nums[randomIndex], nums[rIdx]);Tp pivot = nums[rIdx];int lBoundary = lIdx;int rBoundary = rIdx - 1;for(; ; ++lBoundary, --rBoundary){for (; lBoundary <= rBoundary && nums[lBoundary] < pivot; ++lBoundary) {}for (; lBoundary <= rBoundary && nums[rBoundary] > pivot; --rBoundary) {}if (lBoundary > rBoundary) {break;}std::swap(nums[lBoundary], nums[rBoundary]);}std::swap(nums[rIdx], nums[lBoundary]);return lBoundary;
}

2.2 过程示例

  • 假设 nums = [7, 3, 5, 1, 2, 6, 4],随机选择的pivot下标为5,即6与最右的4交换,得到 nums = [7, 3, 5, 1, 2, 4, 6]
  • 分区指针起始如图:left (lIdx) -> 7, 3, 5, 1, 2, 4 <- right (rIdx), 6(pivot)
  • 左指针移动到第一个大于或等于主元的元素(即7),右指针移动到第一个小于或等于主元的元素(为4):left (lIdx) -> 7, 3, 5, 1, 2, 4 <- right (rIdx), 6(pivot)
  • 交换左右指针处的元素:left (lIdx) -> 4, 3, 5, 1, 2, 7 <- right (rIdx), 6(pivot)
  • 继续该过程,直到左右指针相遇:4, 3, 5, 1, 2 <- right (rIdx), left (lIdx) -> 7, 6(pivot)
  • 将枢轴元素(当前位于右指针处)与左指针处的元素交换(6和7交换)。

3. 非递归快速排序

3.1 实现

template <typename Tp>
void quickSort(vector<Tp>& nums) {std::stack<std::pair<int, int>> stack;stack.push(std::make_pair(0, nums.size() - 1));while (!stack.empty()) {std::pair<int, int> current = stack.top();stack.pop();int lIdx = current.first;int rIdx = current.second;if (lIdx < rIdx) {int boundary = partition(nums, lIdx, rIdx);stack.push(std::make_pair(lIdx, boundary - 1));stack.push(std::make_pair(boundary + 1, rIdx));}}
}

4. 递归快速排序

4.1 实现

template <typename Tp>
void qSortRecursion(vector<Tp>& nums, const int& lIdx, const int& rIdx) {if (lIdx < rIdx) {int boundary = partition(nums, lIdx, rIdx);qSortRecursion(nums, lIdx, boundary - 1);qSortRecursion(nums, boundary + 1, rIdx);}
}template <typename Tp>
void quickSort(vector<Tp>& nums) {qSortRecursion(nums, 0, nums.size() - 1);
}

5. 有问题的Partition

5.1 实现

大量重复元素会超时:

template <typename Tp>
int partition(vector<Tp>& nums, int lIdx, int rIdx) {// 较为有序时, 避免超时int randIdx = lIdx + rand() % (rIdx - lIdx + 1);std::swap(nums[randIdx], nums[rIdx]);int pivot = nums[rIdx];int boundary = lIdx;for (int idx = lIdx; idx < rIdx; ++idx) {if (nums[idx] < pivot) {std::swap(nums[idx], nums[boundary]);++boundary;}}std::swap(nums[boundary], nums[rIdx]); // pivotreturn boundary;
}

通过内排序Introsort修复:

template <typename Tp>
void quickSort(vector<Tp>& nums) {double recThreshold = log10(nums.size()) / log10(2);int recDepth = 0;std::stack<std::pair<int, int>> stack;stack.push(std::make_pair(0, nums.size() - 1));while (!stack.empty()) {++recDepth;if (recDepth >= recThreshold) {heapSort(nums);break;}std::pair<int, int> current = stack.top();stack.pop();int lIdx = current.first;int rIdx = current.second;if (lIdx < rIdx) {int boundary = partition(nums, lIdx, rIdx);stack.push(std::make_pair(lIdx, boundary - 1));stack.push(std::make_pair(boundary + 1, rIdx));}}
}

6. 三中位数主元选择

6.1 实现

template <typename Tp>
int choosePivot(vector<Tp>& nums, int lIdx, int rIdx) {int mid = lIdx + (rIdx - lIdx) / 2;if (nums[lIdx] > nums[mid]) {std::swap(nums[lIdx], nums[mid]);}if (nums[mid] > nums[rIdx]) {std::swap(nums[mid], nums[rIdx]);}if (nums[lIdx] > nums[mid]) {std::swap(nums[lIdx], nums[mid]);}return mid;
}template <typename Tp>
int partition(vector<Tp>& nums, int lIdx, int rIdx) {int pivotIdx = choosePivot(nums, lIdx, rIdx);std::swap(nums[pivotIdx], nums[rIdx]);Tp pivot = nums[rIdx];int lBoundary = lIdx;int rBoundary = rIdx - 1;for(; ; ++lBoundary, --rBoundary){for (; lBoundary <= rBoundary && nums[lBoundary] < pivot; ++lBoundary) {}for (; lBoundary <= rBoundary && nums[rBoundary] > pivot; --rBoundary) {}if (lBoundary > rBoundary) {break;}std::swap(nums[lBoundary], nums[rBoundary]);}std::swap(nums[rIdx], nums[lBoundary]);return lBoundary;
}

7. 总结

快速排序作为一种现代化的排序算法,通过分治策略和递归实现,高效地解决了大多数排序问题。使用最优的Partition算法和三中位数主元选择可以有效优化快速排序的性能,并避免最坏情况的出现。

这篇关于【CS.AL】八大排序算法 —— 快速排序全揭秘:从基础到优化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044991

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》:本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对(Key-Value)存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2