归并排序、快速排序c++实现

2024-09-04 07:18
文章标签 c++ 实现 快速 归并 排序

本文主要是介绍归并排序、快速排序c++实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

归并排序

假定由小到大排。
1、思想:
分解:二分为左右两部分;
递归地对两边归并:对左边归并,对右边归并
合并:合并左右为一个。
2、code:
输入:
6
60 90 50 30 20 40
输出:
20 30 40 50 60 90

#include <iostream>
#include <vector>using namespace std;//合并v[low...mid]和v[mid+1...high]
void merge(vector<int> &v, int low, int mid, int high){//这里temp,引起空间复杂度O(N)vector<int> temp(high-low+1, 0);//实时的high-low+1int p1= low;//指向左边的int p2= mid+1;//指向右边的int p3= 0;//指向新空间tempwhile(p1<=mid && p2<=high){if(v[p1]<=v[p2]){temp[p3]= v[p1];p1++;}else{temp[p3]= v[p2];p2++;}p3++;}while(p1<= mid){temp[p3++]= v[p1++];}while(p2<=high){temp[p3++]= v[p2++];}//把temp赋值到原数组里的对应区域  别忘记for(int i=0; i<(int)(high-low+1);++i){v[low+i]=temp[i];//是low+i,不是i哦}
}void mergeSort(vector<int> &v, int low, int high){if(low== high)//递归终止条件:只有一个元素的时候,每组就都是有序的了return;//分解:一分为二int mid= low+ ((high-low)>>1);//递归归并左边mergeSort(v, low, mid);//递归归并右边mergeSort(v, mid+1, high);//合并左右为一个merge(v, low, mid, high);
}int main()
{int n;cin>> n;vector<int> v;int num;for(int i=0; i<n; ++i){cin>> num;v.push_back(num);}int len=(int)v.size();int low=0, high=len-1;mergeSort(v, low, high);for(auto num: v){cout<< num<<" ";}cout<<endl;return 0;
}

快速排序

假定由小到大排。
输入:
6
60 90 50 30 20 40
输出:
20 30 40 50 60 90
1、思想:
每一趟排序前定一个枢轴;
一趟排序下来,比枢轴小的在其左边,比枢轴大的在其右边;
递归快排左边部分,递归快排右边部分。

具体每一躺怎么排?
双指针,逆向扫描,正向扫描。
逆向扫描:当前数一直大于枢轴就继续扫描,不大于了跳出。同时将该小数放到左边去。
逆向扫描:当前数一直小于枢轴就继续扫描,不小于了跳出。同时将该大数放到右边去。
重复上述过程,直到正向逆向扫描相遇,终止(扫描完了)。

2、code:

#include <iostream>
#include <vector>using namespace std;int partition(vector<int> &v, int low, int high){//定枢轴int pivot= v[low];//扫描while(low< high){//逆向扫描  记得覆盖while(low< high && v[high]> pivot)  high--;v[low]= v[high];//正向扫描  记得覆盖while(low< high && v[low]< pivot)   low++;v[high]= v[low];}//枢轴落地v[low]= pivot;//OR v[high]=pivot;return low;
}void quickSort(vector<int> &v, int low, int high){if(low< high){//一趟排完后,枢轴落地的indexint index= partition(v, low, high);//递归快排枢轴落地位置的左边quickSort(v, low, index-1);//递归快排枢轴落地位置的右边quickSort(v, index+1, high);}
}int main()
{int n;cin>> n;vector<int> v;int num;for(int i=0; i<n; ++i){cin>> num;v.push_back(num);}int len=(int)v.size();int low=0, high=len-1;quickSort(v, low, high);for(auto num: v){cout<< num<<" ";}cout<<endl;return 0;
}

这篇关于归并排序、快速排序c++实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中使用Java Mail实现邮件服务功能示例

《Java中使用JavaMail实现邮件服务功能示例》:本文主要介绍Java中使用JavaMail实现邮件服务功能的相关资料,文章还提供了一个发送邮件的示例代码,包括创建参数类、邮件类和执行结... 目录前言一、历史背景二编程、pom依赖三、API说明(一)Session (会话)(二)Message编程客

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》:本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历:2、Java8 Stream API:3、Apache Commons

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

C#提取PDF表单数据的实现流程

《C#提取PDF表单数据的实现流程》PDF表单是一种常见的数据收集工具,广泛应用于调查问卷、业务合同等场景,凭借出色的跨平台兼容性和标准化特点,PDF表单在各行各业中得到了广泛应用,本文将探讨如何使用... 目录引言使用工具C# 提取多个PDF表单域的数据C# 提取特定PDF表单域的数据引言PDF表单是一

使用Python实现高效的端口扫描器

《使用Python实现高效的端口扫描器》在网络安全领域,端口扫描是一项基本而重要的技能,通过端口扫描,可以发现目标主机上开放的服务和端口,这对于安全评估、渗透测试等有着不可忽视的作用,本文将介绍如何使... 目录1. 端口扫描的基本原理2. 使用python实现端口扫描2.1 安装必要的库2.2 编写端口扫

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言

MySQL分表自动化创建的实现方案

《MySQL分表自动化创建的实现方案》在数据库应用场景中,随着数据量的不断增长,单表存储数据可能会面临性能瓶颈,例如查询、插入、更新等操作的效率会逐渐降低,分表是一种有效的优化策略,它将数据分散存储在... 目录一、项目目的二、实现过程(一)mysql 事件调度器结合存储过程方式1. 开启事件调度器2. 创

使用Python实现操作mongodb详解

《使用Python实现操作mongodb详解》这篇文章主要为大家详细介绍了使用Python实现操作mongodb的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、示例二、常用指令三、遇到的问题一、示例from pymongo import MongoClientf

SQL Server使用SELECT INTO实现表备份的代码示例

《SQLServer使用SELECTINTO实现表备份的代码示例》在数据库管理过程中,有时我们需要对表进行备份,以防数据丢失或修改错误,在SQLServer中,可以使用SELECTINT... 在数据库管理过程中,有时我们需要对表进行备份,以防数据丢失或修改错误。在 SQL Server 中,可以使用 SE

基于Go语言实现一个压测工具

《基于Go语言实现一个压测工具》这篇文章主要为大家详细介绍了基于Go语言实现一个简单的压测工具,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录整体架构通用数据处理模块Http请求响应数据处理Curl参数解析处理客户端模块Http客户端处理Grpc客户端处理Websocket客户端