【Leetcode刷题(数据结构)】:三路划分与三数随机取中的思想实现快速排序的再优化

在这里插入图片描述
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中
的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右
子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if(right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div+1, right)QuickSort(array, div+1, right);
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉
树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有:

1. hoare版本

在这里插入图片描述
看懂了动图那么我们的代码实现如下

// Hoare
int PartSort1(int* a, int left, int right)
{//int midi = GetMidi(a, left, right);//Swap(&a[left], &a[midi]);int keyi = left;while (left < right){// 找小while (left < right && a[right] >= a[keyi]){--right;}// 找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  // mid是最大值{return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) // mid是最小{return left;}else{return right;}}
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}

2.挖坑法

在这里插入图片描述
代码实现如下

// 挖坑法
int PartSort2(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];// 保存key值以后,左边形成第一个坑int hole = left;while (left < right){// 右边先走,找小,填到左边的坑,右边形成新的坑位while (left < right && a[right] >= key){--right;}a[hole] = a[right];hole = right;// 左边再走,找大,填到右边的坑,左边形成新的坑位while (left < right && a[left] <= key){++left;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  // mid是最大值{return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) // mid是最小{return left;}else{return right;}}
}
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){ printf("%d ", a[i]);}printf("\n");
}

3.前后指针版本

在这里插入图片描述
代码实现如下

// 前后指针
int PartSort3(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);return prev;
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  // mid是最大值{return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) // mid是最小{return left;}else{return right;}}
}

2.3.2 快速排序优化

  1. 三数取中法选key
  2. 递归到小的子区间时,可以考虑使用插入排序
    在这里插入图片描述
    快速排序的特性总结:
  3. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  4. 时间复杂度:O(N*logN)
    在这里插入图片描述
  5. 空间复杂度:O(logN)
  6. 稳定性:不稳定
    在这里插入图片描述

三路划分与三数随机取中的思想实现快速排序的再优化

在这里插入图片描述
这是题目 我们按照上面所讲的(这里我们使用快速排序的方法来实现 所以代码可以拷贝粘贴 所以我们就不再继续赘述)
在这里插入图片描述
看一下这个图片 我们定义一个变量将key保存起来以便后续比较不会丢失key的数据
定义一个cur表示当前数据 然后根据我的蓝色字体部分思考一下 ++L,–R的各自的含义
最后就会形成一个左边为小于key的数 中间为等于key的数 右边为大于key的数 这样做的好处是如果避免大量的重复数据带来的不利影响 希望大家能够理解
这样以来 我们中间的和key相等的数据就不用再次递归了 只用递归左和右的两组数据了 是不是很方便
但是这里还有一个问题就是三数取中我们还要再次优化一下避免Leetcode判题太严格导致我们所有测试用例通过了 但是超时了
下面给大家看一下详细代码和报错示例
在这里插入图片描述
在这里插入图片描述
希望我的讲解能够最大限度的帮助到你 希望你今天收获满满 我们下一篇文章再见!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Asp.net core Web Api 配置swagger中文

启动项目&#xff0c;如图&#xff1a; 原来是英文的&#xff0c;我们要中文的&#xff0c;WeatherForecastController.cs是一个示例&#xff0c;删除即可&#xff0c;WeatherForecast.cs同时删除&#xff0c;当然不删除也行&#xff0c;这里是删除&#xff0c;创建自己的控制器…

在不安全的集群上启用 Elasticsearch Xpack 安全性

本博文详细描述如何把一个没有启动安全的 Elasticsearch 集群升级为一个带有 HTTPS 访问的启用 Elasticsearch xpack 安全的集群。 为了增强 Elasticsearch 集群的安全性&#xff0c;你需要执行完全集群重启&#xff0c;并在客户端进行一些更改。 启用身份验证后&#xff0c;所…

linux环境下使用lighthouse与selenium

一、安装谷歌浏览器、谷歌浏览器驱动、lighthouse shell脚本 apt update && apt -y upgrade apt install -y curl curl -fsSL https://deb.nodesource.com/setup_18.x | bash apt install -y nodejs apt install -y npm npm install -g lighthouse apt-get install -y …

vue 01

安装vscode 按照如下方式汉化 给vscode 安装插件 Vetur 安装node.js 下载地址https://nodejs.org/en/download/&#xff0c;选择windows msi 在cmd下检查如下&#xff1a; 检查nodejs版本:node --version 检查npm的安装版本&#xff1a;npm -v 执行命令&#xff1a; npm i…

【机器学习】PyTorch-MNIST-手写字识别

文章目录 前言完成效果一、下载数据集手动下载代码下载MNIST数据集&#xff1a; 二、 展示图片三、DataLoader数据加载器四、搭建神经网络五、 训练和测试第一次运行&#xff1a; 六、优化模型第二次优化后运行&#xff1a; 七、完整代码八、手写板实现输入识别功能 前言 注意…

Android12之报错 error: BUILD_COPY_HEADERS is obsolete(一百六十七)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…

OTN较WDM系统的 升级功能

文章目录 1、增加运维规则&#xff0c;具体措施是增加了帧结构&#xff0c;提升业务的监控管理运维能力。2、增加电交叉功能&#xff0c;使得OTN系统可以分别处理客户业务信号和波分信号。 OTN较WDM系统的 升级功能主要表现在下面两方面&#xff1a; 1、增加运维规则&#xff0…

leetcode:507. 完美数(python3解法)

难度&#xff1a;简单 对于一个 正整数&#xff0c;如果它和除了它自身以外的所有 正因子 之和相等&#xff0c;我们称它为 「完美数」。 给定一个 整数 n&#xff0c; 如果是完美数&#xff0c;返回 true&#xff1b;否则返回 false。 示例 1&#xff1a; 输入&#xff1a;num…

power point导出pdf保留字体

在 slides 中用到非自带的字体&#xff0c;如 [1]&#xff0c;想导出成 pdf 文件&#xff08;因为导出成图&#xff0c;如 png&#xff0c;放大会蒙&#xff09;&#xff0c;并在别人电脑里也保留字体。除了让别人也装上相应字体&#xff0c;可以&#xff1a; 参考 [2]&#x…

OpenHarmony页面级UI状态存储:LocalStorage

LocalStorage 是页面级的 UI 状态存储&#xff0c;通过 Entry 装饰器接收的参数可以在页面内共享同一个 LocalStorage 实例。LocalStorage 也可以在 UIAbility 内&#xff0c;页面间共享状态。 本文仅介绍 LocalStorage 使用场景和相关的装饰器&#xff1a;LocalStorageProp 和…

关于RNNoise、webrtc_ns、三角带通滤波器、对数能量

语音特征参数MFCC提取过程详解 其中讲解了&#xff1a;三角带通滤波器 、计算每个滤波器组输出的对数能量、对数能量、经离散余弦变换&#xff08;DCT&#xff09;得到MFCC系数 推荐阅读某乎这位大佬的全部文章&#xff1a; 下面是几篇出自这位大佬的很好的文章&#xff1a; …

Java前后端交互实现班级管理(查询)

1&#xff0c;数据库创建存储专业信息的表 2&#xff0c;后端&#xff1a; 连接数据库工具类DBUtil.java&#xff1a; package com.ffyc.webserver.util;import java.sql.*;public class DButils {static {try {Class.forName("com.mysql.cj.jdbc.Driver");} catch…

静态IP怎么设置网速快?

随着互联网的普及&#xff0c;越来越多的人需要连接到互联网。大多数人使用动态IP来连接&#xff0c;但有时您可能需要使用静态IP。如果您使用静态IP&#xff0c;那么您需要设置一个静态IP地址。这通常是在路由器或计算机上完成的。 首先&#xff0c;您需要了解什么是静态IP地址…

iOS——Manager封装网络请求

在之前的项目里&#xff0c;我们都是把网络请求写在viewController的viewDidLoad&#xff0c;而实际中使用的时候并不能这么简单&#xff0c;对于不同的需要&#xff0c;我们需要有不同的网络请求。所以我们可以用单例模式创建一个全局的Manager类&#xff0c;用实例Manager来执…

Prompt 驱动架构设计:探索复杂 AIGC 应用的设计之道?

你是否曾经想过&#xff0c;当你在 Intellij IDEA 中输入一个段代码时&#xff0c;GitHub 是如何给你返回相关的结果的&#xff1f;其实&#xff0c;这背后的秘密就是围绕 Prompt 生成而构建的架构设计。 Prompt 是一个输入的文本段落或短语&#xff0c;用于引导 AI 生成模型执…

21.Hadoop在Windows环境下的下载安装配置超详细版

Hadoop在Windows环境下的下载安装配置超详细版 本文章所需下载安装软件&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1jIQyy0VHuPvQZ8-n_Zq0pg?pwd1017 hadoop的Windows化安装步骤是非常麻烦的&#xff0c;如果有一步出错将导致得充头从来。 环境配置 前置依赖1&…

Bootstrap的警告框组件

可以利用类alert实现警告框组件。。 01-基本的警告框组件使用示例 示例代码如下&#xff1a; <!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>警告框</title><meta name"viewport" content"wi…

vite 使用本地 ip + localhost 访问服务

vite 使用本地 ip localhost 访问服务 在 vite.config.js 中&#xff0c;如果未配置 server.host&#xff0c;默认服务将以 localhost 进行启动&#xff0c;此时我们可以通过 localhost:port 或 127.0.0.1:port 进行应用访问。 import { resolve } from path function pathRes…

Hadoop3教程(九):MapReduce框架原理概述

文章目录 简介参考文献 简介 这属于整个MR中最核心的一块&#xff0c;后续小节会展开描述。 整个MR处理流程&#xff0c;是分为Map阶段和Reduce阶段。 一般&#xff0c;我们称Map阶段的进程是MapTask&#xff0c;称Reduce阶段是ReduceTask。 其完整的工作流程如图&#xff…

开源酒店预订订房小程序源码系统+多元商户 前端+后端完整搭建教程 可二次开发

大家好啊&#xff0c;罗峰今天来给大家分享一款酒店预订订房小程序源码系统&#xff0c;这款系统进行了全新的升级&#xff0c;从原来的单门店升级成了多门店&#xff0c;可以自由切换账号&#xff0c;统一管理。功能强大。以下是部分代码截图&#xff1a; 酒店预订订房小程序源…