当前位置: 首页 > 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;
}

http://www.lryc.cn/news/433803.html

相关文章:

  • DBC中一种特殊的特殊的Signal—多路复用Signal
  • 前端基础面试题·第三篇——JavaScript(其三)
  • MacBook真的不能打游戏吗?Mac打游戏会损坏电脑吗?苹果电脑怎么玩游戏
  • 安卓逆向(之)真机root(红米手机)
  • 关于转行网络安全的一些建议
  • (六十五)第 10 章 内部排序(希尔排序)
  • 802.11 中 scrambler的matlab仿真
  • centos 服务器 多网卡 ip 地址 设置
  • 什么是大数据、有什么用以及学习内容
  • ZBrush与Blender雕刻功能哪个更好些?
  • 软件工程技术专业软件开发综合实训室解决方案
  • 链动2+1:高效用户留存与增长的商业模式解析
  • Python 调用手机摄像头
  • E5053A 微波下变频器
  • 记录:uniapp直播的弹幕的样式修改与发送弹幕会自动滚动到底部两个技巧
  • 【流程设计】JAVA系统集成activiti工作流,流程设计器,在线审批,会签,驳回,流程图查看(实际多套系统运用案例分析)
  • Debezium系列之:大规模应用debezium server采集数据库,从每个Debezium Server中导出JMX采集指标
  • QY-SW 浮子水位计 RS485 LCD显示屏
  • 橘子学ES实战操作之管道类型Ingest pipelines的基本使用
  • VScode:前端开发中的常用快捷键和技巧
  • Radmin-同一局域网只需IP就可以控制电脑
  • 【附答案】C/C++ 最常见50道面试题
  • C++音视频开发笔记目录
  • spring项目整合log4j2日志框架(含log4j无法打印出日志的情况,含解决办法)
  • Linux网络:应用层协议http/https
  • transforemr网络理解
  • C++插件管理系统
  • MyBatis 方法重载的陷阱及解决方案
  • STM32 ADC+DMA导致写FLASH失败
  • Python AttributeError: ‘dict_values’ object has no attribute ‘index’