【算法】快速排序的基本思想、优化 | 挖坑填补法和区间分割法

创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步!
更多算法分析与设计知识专栏:算法分析🔥
给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

在这里插入图片描述


目录

  • 一、挖坑填补法
  • 二、区间分割法
  • 三、快排的优化:

快排的基本思想:先确定一个标准值,将比标准值小的元素放在标准值的左侧,比标准值大的元素放在右侧,左右部分分别重复以上的操作,直到整个数组有序。

快速排序是基于分治策略的排序算法

一、挖坑填补法

  1. 选择一个基准元素
  2. 将基准元素挖出,形成一个坑
  3. 从右向左遍历数组,找到第一个比基准元素小的元素,将其填入空坑中,并将此位置视为新的坑
  4. 从左向右遍历数组,找到第一个比基准元素大的元素,将其填入新的空坑中,并将此位置视为新的坑
  5. 重复过程,直到左右指针相遇
  6. 最后将基准元素填入坑中,此时基准元素左边的所有元素都比它小,右边的所有元素都比它大。
  7. 对基准元素左边右边的子数组递归地进行上述操作,直到整个数组有序

image.png

C++代码:

#include <iostream>
#include <cmath>
using namespace std;

int partition(int arr[], int left, int right)
{
    // 确定标准值,保存起来
    int standard = arr[left];

    //使用双指针从两端开始,将比标准值大的数放到标准值右侧,小于标准值的放到左侧
    while (left < right)
    {
        //从右到左(right到left)找到比标准值小的
        //如果遇到的值大于等于标准值,则跳过 right--
        while (left < right && arr[right] >= standard)
        {
            right--;
        }
        //找到了比标准值小的值arr[right],放到左边的left坑中
        arr[left] = arr[right];

        //从左到右(left到right)找到比标准值大的
        //如果遇到的值小于等于标准值,则跳过 left++
        while (left < right && arr[left] <= standard)
        {
            left++;
        }
        //找到了比标准值大的值arr[left],放到左边的right坑中
        arr[right] = arr[left];
    }
    //中间的坑放入标准值
    arr[left] = standard;
    //返回标准值的下标
    return left;
}

void quicksort(int arr[], int left, int right)
{
    if (arr == NULL || left >= right) return;
    int standard = partition(arr, left, right);
    quicksort(arr, left, standard - 1);
    quicksort(arr, standard + 1, right);
}

void print(int arr[], int len)
{
    if (arr == NULL || len <= 0) return;
    for (int i = 0; i < len; i++)
    {
        std::cout << arr[i] << " ";
    }std::cout << endl;
}

int main()
{
    int arr[] = { 5, 1, 7, 0, 4, 3, 4, 9, 6 };
    int len = sizeof(arr) / sizeof(arr[0]);
    cout << "------------------------------" << endl << "原始序列:";
    print(arr, len);
    quicksort(arr, 0, len - 1);
    cout << "------------------------------" << endl << "排序后序列:";
    print(arr, len);
    return 0;
}

image.png

二、区间分割法

#include <iostream>
#include <cmath>
using namespace std;

int partition(int arr[], int left, int right)
{
    int nSmall = left - 1;

    for (left; left < right; left++)
    {
        if (arr[left] < arr[right])
        {
            //小区间扩张
            if (++nSmall != left)
            {
                arr[nSmall] = arr[nSmall] ^ arr[left];
                arr[left] = arr[nSmall] ^ arr[left];
                arr[nSmall] = arr[nSmall] ^ arr[left];
            }
        }
    }
    //将标准值放入
    if (++nSmall != right)
    {
        arr[nSmall] = arr[nSmall] ^ arr[right];
        arr[right] = arr[nSmall] ^ arr[right];
        arr[nSmall] = arr[nSmall] ^ arr[right];
    }
    return nSmall;
}
void print(int arr[], int len)
{
    if (arr == NULL || len <= 0) return;
    for (int i = 0; i < len; i++)
    {
        std::cout << arr[i] << " ";
    }std::cout << endl;
}

int main()
{
    int arr[] = { 5, 1, 7, 0, 4, 3, 4, 9, 6 };
    int len = sizeof(arr) / sizeof(arr[0]);
    cout << "------------------------------" << endl << "原始序列:";
    print(arr, len);
    quicksort(arr, 0, len - 1);
    cout << "------------------------------" << endl << "排序后序列:";
    print(arr, len);
    return 0;
}

三、快排的优化:

  • 1.标准值的选取:选取三个数字(头、尾、中间),选择大小为中间值
  • 2.分割到数据较少时,不再使用快排,使用插入排序
  • 3.使用栈取代递归
  • 4.尾递归

以下为使用了标准值三选一、按情况使用插入排序的优化后代码:

class Solution {
public:
    void swap (vector<int>& nums, int i, int j) 
    {     
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    } 
    void insertSort (vector<int>& nums, int left, int right) 
    {
        for (int i = left+1; i <= right; i++) 
        {
            int temp = nums[i];
            int j = i-1;
            for (j = i-1; j >= 0; j--) 
            {
                if (temp < nums[j]) 
                {
                    nums[j+1] = nums[j];
                    continue;
                } 
                break;
            }
            nums[j+1] = temp;
        }
    } 

    int place(vector<int>& nums,int left,int right)
    {
        //标准值三选一
            int mid = left + (right-left)/2;
            if (nums[left] > nums[right]) swap(nums,left,right);
            if (nums[mid] > nums[right]) swap(nums,mid,right);
            if (nums[mid] > nums[left]) swap(nums,mid,left); 
        int standard = nums[left];
        while(left < right)
        {
            while(left<right&&nums[right]>standard)
            {
                right--;
            }
            nums[left] = nums[right];
            while(left<right&&nums[left]<standard)
            {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = standard;
        return left;
    }
    void quickSort(vector<int>& nums,int left,int right)
    {
        //分割到数据较少时,不再使用快排,使用插入排序
        if (right - left <= 5) 
        {
                insertSort(nums,left,right);
                return;
        }     
        
        if(nums.size() == 0 || left >= right) return;
        
        int standard = place(nums,left,right);
        quickSort(nums,left,standard-1);
        quickSort(nums,standard+1,right);
    }

    vector<int> sortArray(vector<int>& nums) 
    {
        quickSort(nums,0,nums.size()-1);
        return nums;
    }
};

在这里插入图片描述

大家的点赞、收藏、关注将是我更新的最大动力! 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大,我会继续不断努力提供有价值的内容!如果本文哪里有错误的地方还请大家多多指出(●'◡'●)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546756.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spire.PDF for .NET【文档操作】演示:合并 PDF 文档

需要合并 PDF 的原因有很多。例如&#xff0c;合并 PDF 文件允许您打印单个文件&#xff0c;而不是为打印机排队多个文档&#xff0c;组合相关文件通过减少要搜索和组织的文件数量来简化管理和存储多个文档的过程。在本文中&#xff0c;您将学习如何使用Spire.PDF for .NET将多…

STM32移植嵌入式开源按键框架

目录 STM32移植嵌入式开源按键框架 MultiButton简介 multi_button.c文件 multi_button.h文件 按键事件 案例使用方法 学习剖析 STM32移植嵌入式开源按键框架 今天移植了一款嵌入式按键框架工程MultiButton&#xff0c;MultiButton是一个小巧简单易用的事件驱动型按键驱动…

OSCP靶场--Wombo

OSCP靶场–Wombo 考点(redis 主从复制RCE ) 1.nmap扫描 ## ┌──(root㉿kali)-[~/Desktop] └─# nmap -sV -sC 192.168.153.69 -p- -Pn --min-rate 2500 Starting Nmap 7.92 ( https://nmap.org ) at 2024-04-13 07:33 EDT Nmap scan report for 192.168.153.69 Host is u…

代理IP服务商:选择、优势与未来趋势

目录 一、代理IP服务商的选择 二、代理IP的优势 三、代理IP的未来发展趋势 在网络爬虫、数据采集、SEO优化等网络应用中&#xff0c;代理IP扮演着不可或缺的角色。代理IP服务商则是提供这些代理IP资源的主体&#xff0c;如何选择合适的服务商&#xff0c;以及代理IP的优势和…

风速Weibull分布和光伏Beta分布的参数拟合方法(含matlab算例)

在风光场景生成、随机优化调度等研究中&#xff0c;常常假设风速服从Weibull分布&#xff0c;太阳辐照度服从Beta分布。那我们如何得到两个分布的参数呢&#xff1f;文本首先介绍了风速Weibull分布和辐照度Beta分布的基本概率模型及其性性质&#xff0c;之后以MATLAB代码为例阐…

【JAVA基础篇教学】第七篇:Java异常类型说明

博主打算从0-1讲解下java基础教学&#xff0c;今天教学第七篇&#xff1a;Java异常类型说明。 在Java中&#xff0c;错误&#xff08;Error&#xff09;是Throwable类及其子类的实例&#xff0c;它们通常表示严重的问题&#xff0c;无法通过程序来处理&#xff0c;而是需要进…

javaWeb项目-外面点餐系统功能介绍

项目关键技术 开发工具&#xff1a;IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7 框架&#xff1a;ssm、Springboot 前端&#xff1a;Vue、ElementUI 关键技术&#xff1a;springboot、SSM、vue、MYSQL、MAVEN 数据库工具&#xff1a;Navicat、SQLyog 1、Spring Boot框架 …

vue3第十八节(diff算法)

引言&#xff1a; 上一节说了key的用途&#xff0c;而这个key属性&#xff0c;在vue的vnode 中至关重要&#xff0c;直接影响了虚拟DOM的更新机制&#xff1b; 什么场景中会用到diff算法 如&#xff1a;修改响应式属性需要重新渲染页面&#xff0c;会重新执行render渲染函数返…

AndroidStudio 导出aar包,并使用

打包 1、确认当前选项是否勾选&#xff0c;如未勾选请先勾选。 2、勾选完成后重启Android Studio。 3、重启完成后&#xff0c;选中要打包的module 4、打包完成 使用 1.在项目中新建libs,放入aar文件。 2.修改配置 添加如下代码 flatDir {dirs("libs")}3.修改app…

MongoDB 使用

1 引用依赖包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-mongodb</artifactId></dependency>2 配置文件配置mongodb资料 # MongoDB连接信息 spring.data.mongodb.host 192.168.23.…

ESP32_IDF前端命令开发全过程

ESP32 IDF前端命令开发全过程 开端1. 创建新工程(create-project)2. 创建新组件(create--component)目前文件结构 3. 设置目标芯片4. 配置项目5. 编译工程6. 烧录程序7. 打开监视器8. 一次性编译烧录并打开监视器9. 擦除设备flash10. 查询内存剩余11. 清除编译文件 仅供本人查阅…

【位运算】Leetcode 消失的两个数字

题目解析 面试题 17.19. 消失的两个数字 算法讲解 我们将这两个数组异或在一起&#xff0c;最后的结果就是a ^ b(缺失的两个数字)的结果&#xff0c;这两个缺失的数字一定是不相同的&#xff0c;所以我们就寻找他们第一个比特位是1的那个位置&#xff0c;异或的原理是&#xf…

为了执行SQL语句,MySQL的架构是怎样设计的

1. 把MySQL当个黑盒子一样执行SQL语句 上一讲我们已经说到&#xff0c;我们的系统采用数据库连接池的方式去并发访问数据库&#xff0c;然后数据库自己其实也会维护一个连 接池&#xff0c;其中管理了各种系统跟这台数据库服务器建立的所有连接 我们先看下图回顾一下 当我们的…

WordPress用户福音:Elementor Pro国产版替代方案,全新中文界面更懂你

如果你正在考虑创建自己的网站&#xff0c;那么在第一次谷歌搜索时&#xff0c;你可能已经看到了WordPress、Elementor和网站构建器这些专业名称。WordPress是最受欢迎的网站平台之一&#xff0c;这不难理解&#xff1a;它高度可定制&#xff0c;易于学习&#xff0c;而且是免费…

第十五届蓝桥杯 javaB组第三题

测试通过了90% 剩下10%不知道哪错了 思路&#xff1a;我想的是用map&#xff0c;k存第几个队列&#xff0c;value存每个子队列的长度&#xff0c;最后给value排序 第一个就最小的也就是是有效元素数量 考试只对了个案例&#xff0c;其它情况没测试。 复盘 回来后经过修改改…

3.00 版本来了!DolphinDB V2.00.12 V3.00.0 正式发布!

一文带你了解 DolphinDB 全新版本升级&#xff01; 本次更新后&#xff0c;3.00.0版本将成为 DolphinDB 的最新版&#xff0c;2.00.12版本变更为稳定版&#xff0c;此前发布的1.30.23版本将成为1.30系列的最后一个版本。接下来&#xff0c;带大家一起看看 DolphinDB V2.00.12 …

Android Studio通过修改文件gradle-wrapper.properties内容下载gradle

一、问题描述 在Android Studio中新建项目后会下载你所新建的项目的activity/gradle/wrapper目录下所配置的gradle-7.3.3-bin.zip包&#xff08;笔者的是该版本包&#xff09;&#xff0c;而大多数时候会下载失败&#xff0c;如下 二、解决办法 新建工程后&#xff0c;取消下…

使用 Fn Project 搭建无服务平台

目录 下载 脚本直接下载 下载可执行文件 上传 启动 Fn 服务 初始化 Fn 工程 创建 app 部署 function 调用 function JSON 入参 官方文档 下载 有两种下载方式 脚本直接下载 直接在服务器执行该命令即可 curl -LSs https://raw.githubusercontent.com/fnproject/…

10、【代理模式】通过引入一个代理对象来控制对原始对象的访问的方式。

你好&#xff0c;我是程序员雪球。 今天我们了解代理模式的原理、静态代理和动态代理的区别、Spring AOP 和动态代理的关系、代理模式的使用场景&#xff0c;以及用 Java 实现一个动态代理示例 一、代理模式的原理 代理模式是一种设计模式&#xff0c;它提供了一种通过引入一个…

【十一】MyBatis Plus 原理分析

MyBatis Plus 原理分析 摘要 Java EE开发中必不可少ORM框架&#xff0c;目前行业里最流行的orm框架非Mybatis莫属了&#xff0c;而Mybatis框架本身没有提供api实现&#xff0c;所以市面上推出了Mybatis plus系列框架&#xff0c;plus版是mybatis增强工具&#xff0c;用于简化My…