当前位置: 首页 > news >正文

快速排序+归并排序代码回顾

快速排序与归并排序简介: 

quick_sort为快速排序,merge_sort为归并排序,两者基于分治的思想;

快速排序,简称快排,它以原来数组中的一个值(我们记为x)作为界限,将比它小的元素放到x的左边,大于x的放到x的右边,一遍之后,x就放到了它应该放到的位置,然后对x左侧的子数组做快排,同理,对于x右侧的子数组继续做快排即可;

归并排序,是将数组的中点作为界限,将处于前50%的值放在左一半,将大小处于后50%的值放在右一半。不考虑顺序。一轮过去,我们继续对数组前半边使用归并排序,同理,对于数组右半边使用归并排序。值得注意的是,归并排序一直这样递归下去,数组将不断被分割为大小为1的单个元素数组。前面我们并没有考虑顺序,现在我们使用一个tmp数组,对于两个已经被切割的子数组中的元素进行排序。对于原来两个数组各自使用一个指针从头到尾遍历,谁小谁就放在tmp数组中,遍历完成之后,如果有一个数组没有遍历完,那说明它的值相对于另一个数组来说值较大,我们直接拷贝到tmp数组中即可。这样tmp数组放的肯定就是已经排好序的元素,我们应该把他放到原数组中去,让它参与下一轮比较。

代码一览:

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<assert.h>
using namespace std;void Swap(int* pa, int* pb) {int temp = *pa;*pa = *pb;*pb = temp;
}
void quick_sort(int q[], int l,int r) {if(l >= r)return;int i = l - 1, j = r + 1;int x = q[(l + r) / 2];while (i < j) {do i++; while (q[i] < x);do j--; while (q[j] > x);if (i < j)Swap(&q[i], &q[j]);}quick_sort(q, l, j), quick_sort(q, j+1,r);//不要把这个忘记了!是j而不是i,如果是后者,模板得换;
}
int tmp[100];
void merge_sort(int q[], int l, int r) {if (l >= r)return;int mid = (l + r) / 2;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r) {if (q[i] < q[j])tmp[k++] = q[i++];else tmp[k++] = q[j++];}while (i <= mid) {tmp[k++] = q[i++];}while (j <= r) {tmp[k++] = q[j++];}for (k = 0, i = l; i <= r; k++,i++) {q[i] = tmp[k];}
}
int main() {int arr[] = { 95,1,45,45,454,5,45,62,64,87,84,36,16,1 };int arr2[] = { 95,1,45,45,454,5,45,62,64,87,84,36,16,1 };int len = sizeof(arr) / sizeof(arr[0]);quick_sort(arr, 0, len - 1);merge_sort(arr2, 0, len - 1);for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}puts("");for (int i = 0; i < len; i++) {printf("%d ", arr2[i]);}puts("");return 0;
}

为了保证随机性,我们亦可以在main函数中使用随机数来初始化数组,其他不变:

int main(){int p[10],q[10];srand(time(NULL));for (int i = 0; i < 10; i++) {p[i] = rand() % 999 + 1;q[i] = rand() % 9999 + 1;}for (int i = 0; i < 10; i++) {printf("%d ", p[i]);}puts("");for (int i = 0; i < 10; i++) {printf("%d ", q[i]);}puts("");quick_sort(p, 0, 9);merge_sort(q, 0, 9);puts("");for (int i = 0; i < 10; i++) {printf("%d ", p[i]);}puts("");for (int i = 0; i < 10; i++) {printf("%d ", q[i]);}puts("");return 0;
}

相关文章:

快速排序+归并排序代码回顾

快速排序与归并排序简介&#xff1a; quick_sort为快速排序&#xff0c;merge_sort为归并排序&#xff0c;两者基于分治的思想&#xff1b; 快速排序&#xff0c;简称快排&#xff0c;它以原来数组中的一个值&#xff08;我们记为x&#xff09;作为界限&#xff0c;将比它小…...

DBC中一种特殊的特殊的Signal—多路复用Signal

前言&#xff1a; DBC设计中一般设计Signal时其实存在三种类型&#xff0c;如下图所示&#xff1a; **1&#xff09;步骤1&#xff0c;鼠标单击展开Message&#xff0c;选中底下的Signal **2&#xff09;步骤2&#xff0c;弹出dialog中选择 map signal **3&#xff09;得到…...

前端基础面试题·第三篇——JavaScript(其三)

1.字符串 (1) 常用方法 1.charAt(index) 返回指定位置的字符,若没找到&#xff0c;则返回空2.charCodeAt(index) 返回指定位置的unicode字符编码,若没找到&#xff0c;则返回空 3.String.concat(str1,str2) 连接多个字符串&#xff0c;并返回新字符串4.String.fromCharCode(co…...

MacBook真的不能打游戏吗?Mac打游戏会损坏电脑吗?苹果电脑怎么玩游戏

MacBook从来都是高端的代名词&#xff0c;超强的性能搭配顶尖的系统&#xff0c;不光处理大型文件时举重若轻&#xff0c;长期使用也不会有明显卡顿。但很多人在需要MacBook一流的生产力同时&#xff0c;也希望能在空闲时体验游戏的乐趣。在大多人的印象里&#xff0c;Mac电脑对…...

安卓逆向(之)真机root(红米手机)

概览&#xff1a; 1, 手机解锁 2, 下载官方系统包&#xff0c;推荐线刷包,取出镜像文件 3, magisk工具修补 官方系统包 4, adb&#xff1a;命令对手机刷 root 5, 完成 6, 小米手机解锁 点击 小米手机解锁OEM官方教程 记得数据线连接手机电脑 工具下载 点击 下载adb(电脑操作…...

关于转行网络安全的一些建议

在当前就业形势下&#xff0c;不少朋友面临转行的困境。网络安全作为一个热门领域&#xff0c;自然也吸引了许多人的目光。本文将就转行网络安全这一话题&#xff0c;提供一些切实可行的建议。 网络安全行业概况 网络安全涵盖了从基础的脚本编写到高级的漏洞研究等多个层面。该…...

(六十五)第 10 章 内部排序(希尔排序)

示例代码 shellSort.h // // 希尔排序实现头文件#ifndef SHELL_SORT_H #define SHELL_SORT_H#include "errorRecord.h"#define NUM 10 #define MAX_SIZE 20#define EQUAL(a, b) ((a) == (b)) #define LESS_THAN(a, b) ((a) < (b)) #define LESS_OR_EQUAL(a, b) ((…...

802.11 中 scrambler的matlab仿真

802.11a和802.11n中的scrambler仿真不可以直接用matlab中的comm.Scrambler函数。因为这个函数实现的是multiplicative scrambling&#xff0c;而802.11a和802.11n中的scrambler使用的是additive scrambling。additive scrambling使用异或操作进行扰码&#xff0c;multiplicativ…...

centos 服务器 多网卡 ip 地址 设置

centos 服务器 多网卡 ip 地址 设置 https://blog.csdn.net/xh_w20/article/details/141574357 cd /etc/sysconfig/network-scripts/ sudo systemctl status network ● network.service - LSB: Bring up/down networkingLoaded: loaded (/etc/rc.d/init.d/network; bad; v…...

什么是大数据、有什么用以及学习内容

目录 1.什么是大数据&#xff1f; 2.大数据有什么用&#xff1f; 2.1商业与营销&#xff1a; 2.2医疗与健康&#xff1a; 2.3金融服务&#xff1a; 2.4政府与公共服务&#xff1a; 2.5交通与物流&#xff1a; 2.6教育与个性化学习&#xff1a; 3.学习大数据需要学习哪…...

ZBrush与Blender雕刻功能哪个更好些?

选择正确的3D软件首先会让你的创作过程更加轻松&#xff0c;尤其是在动画或大片电影制作方面。不同的软件提供不同的功能&#xff0c;并倾向于专注于特定领域&#xff0c;如绘画、动画或雕刻。如果你选择了适合你风格和目标的软件&#xff0c;你可以创作出极具创意的作品。 在…...

软件工程技术专业软件开发综合实训室解决方案

一、行业背景与前景分析 1.1 软件工程技术专业就业前景 近年来&#xff0c;中国的软件行业取得了显著的成就&#xff0c;即便在全球经济受到新冠疫情冲击的情况下&#xff0c;仍保持了强劲的增长势头。据工业和信息化部发布的数据&#xff0c;2021年我国软件和信息技术服务业…...

链动2+1:高效用户留存与增长的商业模式解析

大家好&#xff0c;我是吴军&#xff0c;任职于一家致力于创新的软件开发企业&#xff0c;担任产品经理的职位。今天&#xff0c;我打算深入分析一个历经时间考验且依旧充满活力的商业模式——“链动21”模式&#xff0c;并通过一个具体的案例和相关数据&#xff0c;展示它如何…...

Python 调用手机摄像头

Python 调用手机摄像头 在手机上安装软件 这里以安卓手机作为演示&#xff0c;ISO也是差不多的 软件下载地址 注意&#xff1a;要想在电脑上查看手机摄像头拍摄的内容的在一个局域网里面(没有 WIFI 可以使用 热点 ) 安装完打开IP摄像头服务器 点击分享查看IP 查看局域网的I…...

E5053A 微波下变频器

_XLT新利通_ E5053A 微波下变频器 E5052B SSA 专用的微波下变频器 Keysight E5053A 是一款与 E5052B 信号源分析仪&#xff08;SSA&#xff09;相关的微波下变频器。 如果您需要设计和测试微波或毫米波频率的信号源&#xff0c;E5053A 支持您扩展该分析仪的频率范围。 从…...

记录:uniapp直播的弹幕的样式修改与发送弹幕会自动滚动到底部两个技巧

1、在直播页面的弹幕评论中&#xff0c;我们希望的样式是&#xff1a; 观众名字&#xff1a;评论 而且颜色有所区分&#xff0c;并在同一行显示 2、我们希望在发弹幕的时候可以回自动滚动到自己发的内容那里 一&#xff1a;弹幕样式修改 因为是小白&#xff0c;前端对于样式这…...

【流程设计】JAVA系统集成activiti工作流,流程设计器,在线审批,会签,驳回,流程图查看(实际多套系统运用案例分析)

基于Javavue开发的智能审批系统&#xff0c;低代码平台方案 其他资料&#xff0c;软件资料清单列表部分文档清单&#xff1a;工作安排任务书&#xff0c;可行性分析报告&#xff0c;立项申请审批表&#xff0c;产品需求规格说明书&#xff0c;需求调研计划&#xff0c;用户需求…...

Debezium系列之:大规模应用debezium server采集数据库,从每个Debezium Server中导出JMX采集指标

Debezium系列之:为每个Debezium Server导出JMX采集指标 一、需求背景二、相关技术内容三、仓库下载对应版本的Debezium Server四、设置jmx指标导出内容五、设置采集JMX六、设置数据库采集七、启动Debezium Server八、查看debezium server的jmx采集指标九、插入数据,观察采集十…...

QY-SW 浮子水位计 RS485 LCD显示屏

产品概述 浮子水位计由水位传感器、显示器、传感器支架、浮子、悬索、平衡锤、RS485通信接口等部分组成&#xff0c;是观测水位变化的监测设备&#xff0c;利用浮子跟踪水位升降&#xff0c;以机械方式直接传动记录。使用浮子式水位计需有测井设备(包括进水管)&#xff0c;适合…...

橘子学ES实战操作之管道类型Ingest pipelines的基本使用

简介 我们在使用ES的时候&#xff0c;经常的用法就是把其他数据源比如Mysql的数据灌到ES中。 借用ES的一些功能来提供数据的全文检索以及聚合分析之类的功能。 在这个灌数据的过程中&#xff0c;我们经常会对数据做一些治理&#xff0c;类似ETL的能力。然后把治理后的数据写入…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...