面试准备之九种排序算法之快速排序

server/2024/12/22 15:13:33/

快排的时间复杂度为nlog(n)

实现方式如下:

首先定义一个交换函数swap,一个取两个下标中间下标并返回的函数findpivot。一个主函数用于划分数组,进行实际快排的函数,一个执行数组排序操作的函数。他们之间的关系是主函数首先判断输入起始下标和终点下标之间关系,如果前者大于等于后者则直接返回。否则我们开始下面的过程,调函数findpivot找到起始下标和终点下标的中间下标,将这个下标所指值和末尾下标所指值进行交换。之后将这个数组和起始下标-1以及终点下标和终点下标值传入实际执行数组排序的函数partition,在这个函数中,我们执行一个判断条件为l<r的循环判断(l和r对应起始值为传入参数),如果l < r 并且++l处的值小于pivot(传入数组的末尾下标对应的值),一直while,退出循环后如果l < r并且--r处的值大于pivot,一直while,这样是为了找到左边大于pivot和右边小于pivot的值并进行交换,保证左边都是小于pivot的值,右边都是大于pivot的值,直到l==r。此时这个l也是>= pivot的第一个值。我们将这个值返回作为partition函数的返回值。

之后我们再将数组末尾值和partition函数返回的下标处的值进行交换,将pivot放到一个左边都是小于它,右边都是大于它的位置了。再以这个下标为划分点,左右两边分别递归调用这个主函数,但一个右边下标是该下标值-1,一个左边下标是该下标值+1,另外两个是数组起始和末尾节点,一直持续下去,最后就能得到排序好的数组了。

代码如下:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;inline int findpivot(int i, int j) {return (i + j) / 2;
}void swap(vector<int>& nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}int partition(vector<int>& nums, int l, int r, int pivot) {while (l < r) {while (l < r && nums[++l] <= pivot);while (l < r && nums[--r] >= pivot);if (l < r) swap(nums, l, r);cout << l << r << endl;	} return l;
}void qsort(vector<int>& nums, int start, int end) {if (start >= end) return;int pivotpartition = findpivot(start, end);swap(nums, pivotpartition, end);int k = partition(nums, start - 1, end, nums[end]);swap(nums, k, end);qsort(nums, start, k - 1);qsort(nums, k + 1, end);
}int main() {vector<int> nums;srand(time(0));for (int i = 0; i < 10; i++) nums.push_back(rand() % 65535);for (int i =0; i <nums.size(); i++)cout << nums[i] << ' ';cout << endl;qsort(nums, 0, nums.size() - 1); for (int i = 0; i < nums.size(); i++)cout << nums[i] << ' ';
}


http://www.ppmy.cn/server/26203.html

相关文章

Adobe PS 2023、Adobe Photoshop 2023下载教程、安装教程

Adobe Photoshop &#xff08;<-下载连接&#xff09;简介&#xff1a; Adobe Photoshop是一款广泛使用的图像处理软件&#xff0c;由Adobe公司开发。它提供了许多强大的工具和功能&#xff0c;可以用于图像编辑、合成、修饰、设计等各个领域。用户可以使用Photoshop来调整…

Fastadmin 日常项目常见用法整理

ps&#xff1a;自己使用笔记备用&#xff0c;不间断更新&#xff0c;常见功能点 一&#xff0c;数据库后缀 结尾字符示例类型要求字段说明timerefreshtimebigint/datetime识别为日期时间型数据&#xff0c;自动创建选择时间的组件imagesmallimagevarchar识别为图片文件&#…

大模型公开课-大模型的语言解码游戏学习总结

在当今快速发展的人工智能领域&#xff0c;深度学习作为其中的一项关键技术&#xff0c;正引领着科技的新潮流。而对于初学者来说&#xff0c;了解大型语言模型的解码游戏&#xff0c;对于理解深度学习的基本概念至关重要。本篇博客将对一次关于大型语言模型解码游戏的视频教学…

人形机器人狂潮来袭

奔跑、咖啡拉花、搬箱子、叠衣、分拣物品、吸尘清洁……曾存在于科幻电影中的人形机器人&#xff0c;正加速走进人类社会。 去年以来&#xff0c;伴随着AI大模型浪潮&#xff0c;被视为AI最佳载体的人形机器人似乎驶入了一条快车道&#xff0c;科技巨头纷纷入局&#xff0c;产…

小程序云开发(十六):小程序API实战

&#x1f517; 运行环境&#xff1a;小程序云开发 &#x1f6a9; 撰写作者&#xff1a;左手の明天 &#x1f947; 精选专栏&#xff1a;《python》 &#x1f525; 推荐专栏&#xff1a;《算法研究》 &#x1f510;#### 防伪水印——左手の明天 ####&#x1f510; &#x1f497…

将SSH密钥添加到GitHub账户

1、生成SSH密钥对&#xff1a; 首先&#xff0c;您需要在本地计算机上生成一个新的SSH密钥对。打开终端或命令提示符&#xff0c;然后运行以下命令。请确保替换your_emailexample.com为您GitHub账户关联的电子邮件地址。这里我们使用Ed25519算法&#xff0c;因为它既安全又高效…

【docker】Docker开启远程访问

将构建的镜像自动上传到服务器。 需要开放 Docker 的端口&#xff0c;让我们在本地能连接上服务器的 Docker&#xff0c;这样&#xff0c;才能上传构建的镜像给 Docker。 开启远程访问 首先在服务器打开 Docker 的服务文件 vim /usr/lib/systemd/system/docker.service修改…

监视器和显示器的区别,普通硬盘和监控硬盘的区别

监视器与显示器的区别&#xff0c;你真的知道吗&#xff1f; 中小型视频监控系统中&#xff0c;显示系统是最能展现效果的一个重要环节&#xff0c;显示系统的优劣将直接影响视频监控系统的用户体验满意度。 中小型视频监控系统中&#xff0c;显示系统是最能展现效果的一个重要…