算法导论CLRS 7.3 随机版快速排序

2024-02-25 20:32

本文主要是介绍算法导论CLRS 7.3 随机版快速排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

/*7.3 随机化快速排序*QUICK-SORT*/
#include<iostream>
#include<iomanip>
#include<vector>
#include<ctime>
using namespace std;
typedef vector<int>::iterator ivecIte;size_t chkivIte(ivecIte iteB, ivecIte iteE)
{if(iteE < iteB) {cout<<"wrong in iterator range!"<<endl;exit(0);}return iteE - iteB;
}
ivecIte partition(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{chkivIte(iteB, iteE);//ite1指向大于*(iteE-1)队列的最左边的元素ivecIte ite1 = iteB, ite2;for(ite2 = iteB; iteE-1 != ite2; ++ite2) {if( *ite2 < *(iteE-1)) {if( ite1!= ite2) {//ite1与ite2指向相同时不能使用^*ite1 = *ite1 ^ *ite2;*ite2 = *ite1 ^ *ite2;*ite1 = *ite1 ^ *ite2;}++ite1;}}//如果ite为iteE-1,说明iteE-1指向最大值,要将其排出//而且两者相等时不能用^if(ite1 != iteE-1){*ite1 = *ite1 ^ *(iteE - 1);*(iteE - 1) = *ite1 ^ *(iteE - 1);*ite1++ = *ite1 ^ *(iteE - 1);}return ite1;
}ivecIte rndPartition(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{srand((unsigned)time(NULL));ivecIte iteRnd = iteB + rand() % (iteE-iteB);if(iteRnd != iteE-1) {*iteRnd = *iteRnd ^ *(iteE - 1);*(iteE-1) = *iteRnd ^ *(iteE - 1);*iteRnd = *iteRnd ^ *(iteE - 1);}return partition(ivec, iteB, iteE);
}void rndQuickSort(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{if(1 < iteE-iteB) {ivecIte iteP = rndPartition(ivec, iteB, iteE);rndQuickSort(ivec, iteB, iteP);rndQuickSort(ivec, iteP, iteE);}
}int main() 
{vector<int> ivec;int inData;cout<<"input some integers with end-of-file!"<<endl;while(cin>>inData)ivec.push_back(inData);rndQuickSort(ivec, ivec.begin(), ivec.end());for(ivecIte ite = ivec.begin(); ivec.end() != ite; ++ite) cout<<setw(5)<<*ite;cout<<endl;system("PAUSE");return EXIT_SUCCESS;
}

这篇关于算法导论CLRS 7.3 随机版快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

一文详解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、开启热

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

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

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs