决战排序之巅(二)

news/2024/2/24 8:22:20/文章来源:https://blog.csdn.net/GenshiN__IMPACt_/article/details/135610458

决战排序之巅(二)

        • 排序测试函数 void verify(int* arr, int n)
    • 归并排序
      • 递归方案
          • 代码可行性测试
      • 非递归方案
          • 代码可行性测试
      • 特点分析
    • 计数排序
      • 代码实现
          • 代码可行性测试
      • 特点分析
    • 归并排序 VS 计数排序(Release版本)
      • 说明
        • 1w rand( ) 数据测试
        • 10w rand( ) 数据测试
        • 100w rand( ) 数据测试
        • 1000w rand( ) 数据测试
      • 测试代码
      • 结语

欢迎来到决战排序之巅栏目,
本期给大家带来的是归并排序与计数排序的实现与比较。
在上期决战排序之巅(一)中,给大家带来了插入排序(希尔) 与 选择排序(堆排) 的实现与比较,感兴趣的可以看看。

请添加图片描述

排序测试函数 void verify(int* arr, int n)

主要功能:测试arr数组中的顺序是否全为非升序的顺序。
代码如下:

void verify(int* arr, int n)
{for (int i = 1; i < n; i++){assert(arr[i] >= arr[i - 1]);}
}

如果arr数组中顺序不全为非升序,则assert()直接终止程序;
若全为非升序,则程序可通过该函数。

归并排序

基本思想:采用分治算法,将已有的有序子序列进行合并,得到完全有序的序列;即先使每个子序列有序,再使子序列所合并的序列有序。
归并排序的核心步骤就是:分解与合并。

递归方案

如下图所示:我们可以先将一组数据由大到小逐个分开,再依次合并。
下图绿线为分解,蓝线为合并。我们可以看到,排序数据分解时,当子序列内个数为1 时,不再分解;随后进行依次的合并,"1" "9" 合并为"1 9"的子序列,"5" "6"合并成"5 6"的体序列,同理可得"3 8" "2 7",再让子序列合并,"1 9 6 5"合并成"1 5 6 9""3 8""2 7"合并成"2 3 7 8"。最后两个字序列合并成"1 2 3 5 6 7 8 9"
至此,归并排序完毕。
在这里插入图片描述
具体代码,如下:

void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

void MergeSort(int* a, int n)是我们排序的调用函数,因为他的参数形式不宜用递归实现,所以我们可以写一个子函数void _MergeSort(int* a,int begin,int end ,int* tmp)来实现主要程序的编写,如下:

void _MergeSort(int* a,int begin,int end ,int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);int left1 = begin, right1 = mid;int left2 = mid + 1, right2 = end;int i = 0;while (left1 <= right1 && left2 <= right2){if (a[left1] > a[left2])tmp[i++] = a[left2++];elsetmp[i++] = a[left1++];}while (left1 <= right1){tmp[i++] = a[left1++];}while (left2 <= right2){tmp[i++] = a[left2++];}memcpy(a + begin, tmp, i * sizeof(int));
}

我们先通过以下代码进行归并排序“分解”的实现

	if (begin >= end)return;	int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);

当子序列内个数为1 时,return 返回;当子序列内个数大于1 时,进行以下编写:
有递归可知,此时的小标区间为[begin , mid] 与 [mid + 1 , end]是排好序的子区间,所有此时我们只要将其合并好就可以了。

	int left1 = begin, right1 = mid;int left2 = mid + 1, right2 = end;int i = 0;while (left1 <= right1 && left2 <= right2){if (a[left1] > a[left2])tmp[i++] = a[left2++];elsetmp[i++] = a[left1++];}while (left1 <= right1){tmp[i++] = a[left1++];}while (left2 <= right2){tmp[i++] = a[left2++];}memcpy(a + begin, tmp, i * sizeof(int));

最后将tmp上的数据拷贝到a的[begin , end]区间即可。

代码可行性测试
void _test()
{int n = 100000000;int* arr = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++){arr[i] = rand();}MergeSort(arr, n);verify(arr, n);free(arr);
}

运行结果如下 :
在这里插入图片描述
程序通过verify(int* arr int n)函数,且成功运行,代码无误。

非递归方案

在非递归方案中我们可以利用循环来实现,主要实现过程如下视频所示:

归并排序思想

我们可以定义一个gap并且gap的初始置为1,用来表示子序列的最小个数为1,随后在整体排完相邻两个子序列后,gap乘以2,此时数组内小标区间为 [ n ∗ g a p , n ∗ ( g a p ∗ 2 − 1 ) ] ∪ [ 0 , g a p − 1 ] , n ∈ N + [n * gap , n * (gap * 2-1)]\cup[0 , gap-1] ,n\in N^+ [ngap,n(gap21)][0,gap1],nN+是有序的,如此循环直到, n ≤ g a p n\leq gap ngap时跳出循环,代码如下:

void MergeSortNonR(int* a,int n)
{int* tmp = (int*)malloc(sizeof(int) * n);assert(tmp);int gap = 1;while (n > gap){for (int i = 0; i < n; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;int j = begin1;if (end1 >= n && begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy( a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(tmp);
}

我们先看如何分解,利用gap来确定子序列的元数个数,再利用for循环来实现两个相邻子序列的排序(即下标区间[begin1,end1] , [begin2,end2]的排序)
注意:在分配完区间[begin1,end1] ,和[begin2,end2]后,我们要对区间范围的有效性进行检查,因为非递归的方案通过比较相邻的子序列,gap2的幂次方所增长,适用的数组长度也为2的幂次方,所以我们要对end1 , begin2 , end2进行检查,如果end1 , begin2 大于数组总个数n时,直接break即可,因为此时的[begin1,n-1]已经是有序的了;如果end2大于n则,令end2=n-1,此时我们只要排好[begin1,end2] , [begin2,n-1]即可,具体过程如下:

		for (int i = 0; i < n; i += gap * 2){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + gap * 2 - 1;int j = begin1;if (end1 >= n && begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//合并过程}

合并过程与递归方案相同,但需要注意的是数组拷贝的时候,for循环依次拷贝一次。

代码可行性测试

在这里插入图片描述

程序通过verify(int* arr int n)函数,且成功运行,代码无误。

特点分析

特性:归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度:O(N*logN)
空间复杂度:O(N)
稳定性:稳定

计数排序

基本思想:计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用。

代码实现

实现步骤:

  1. 选出要排序数组a中的最值,再相减求出数组的相对范围 n = m a x − m i n + 1 n = max - min + 1 n=maxmin+1
  2. 用calloc开辟n个空间为tmp
  3. 利用i遍历a,让数组tmp[ a [ i ] − m i n a[i] - min a[i]min]++
  4. 最后,再遍历tmp , 此时tmp数组下标 + min就表示数据的大小,tmp[数组下标]表示该数据的个数,所以在此时为a直接赋值即可。
    具体代码如下:
void CountSort(int* a, int n)
{int max = a[0], min = a[0];int i = 0;for (i = 0; i < n; i++){if (max < a[i]){max = a[i];}if (min > a[i]){min = a[i];}}int* tmp = (int*)calloc((max - min + 1), sizeof(int));assert(tmp);for (i = 0; i < n; i++){tmp[a[i] - min]++;}int j = 0;for (i = 0; i < max - min + 1; i++){int count = tmp[i];while (count--){a[j++] = i + min;}}free(tmp);
}
代码可行性测试

在这里插入图片描述
程序通过verify(int* arr int n)函数,且成功运行,代码无误。

特点分析

特点分析:计数排序在数据范围集中时,效率很高,但是适用范围及场景有限(例如:小数,结构体,字符串无法比较)
时间复杂度:O(MAX(N,范围))
空间复杂度:O(范围)

归并排序 VS 计数排序(Release版本)

说明

以下会分别对1w,10w,100w,1000w的数据进行100次的排序比较,并计算出排一趟的平均值。

下面是用来生成随机数的代码,可以确保正数与负数的随机分布。

	for (i = 0; i < n; i++){if (rand() % 2){arr3[i] = arr2[i] = arr1[i] = -rand() + i;}else{arr3[i] = arr2[i] = arr1[i] = rand() - i;}}

介绍就到这里了,让我们来看看这100次排序中,谁才是你心目中的排序呢?
PS:100次只是一个小小的测试数据,有兴趣的朋友可以在自己电脑上测试更多的来比较哦。

1w rand( ) 数据测试

在这里插入图片描述

10w rand( ) 数据测试

在这里插入图片描述

100w rand( ) 数据测试

在这里插入图片描述

1000w rand( ) 数据测试

在这里插入图片描述

测试代码

void Test_MergeSort_CountSort()
{int n = 10000000;int count = 100;int* arr1 = numcreate(n);int* arr2 = numcreate(n);int* arr3 = numcreate(n);int time1 = 0, time2 = 0, time3 = 0;int tmp = count;while (tmp--){int i = 0;for (i = 0; i < n; i++){if (rand() % 2){arr3[i] = arr2[i] = arr1[i] = -rand() + i;}else{arr3[i] = arr2[i] = arr1[i] = rand() - i;}}int begin1 = clock();MergeSort(arr1, n);int end1 = clock();int begin2 = clock();MergeSortNonR(arr2, n);int end2 = clock();int begin3 = clock();CountSort(arr3, n);int end3 = clock();time1 += end1 - begin1;time2 += end2 - begin2;time3 += end3 - begin3;}printf("MergeSort: %.2f\n", (float)time1/count);printf("MergeSortNonR: %.2f\n", (float)time2 / count);printf("CountSort: %.2f\n", (float)time3 / count);free(arr1);free(arr2);free(arr3);
}

从结果来看,计数排序快于归并排序,但它的局限性无法比较小数,结构体与字符串;
再看归并排序,非递归类的要略胜一筹哦。

结语

看完之后,谁才是你心目中的排序呢?
欢迎留言,让我们一起来期待在下一期 《决战排序之巅(三)》。

以上就是本期的全部内容喜欢请多多关注吧!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_926238.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Kafka 消息不能正常消费问题排查

订单宽表数据不同步 事情的起因是专员在 ze app 上查不到订单了&#xff0c;而订单数据是从 mysql 的 order_search_info 查询的&#xff0c;order_search_info 表的数据是从 oracel 的 BZ_ORDER_INFO 表同步过来的&#xff0c;查不到说明同步有问题 首先重启&#xff0c;同步…

【K8S 】K8S配置资源管理

一、Secret&#xff1a; 1、概念 用来保存密码。token&#xff0c;敏感的K8S资源 这类数据可以直接存放在镜像中&#xff0c;但是放在Secret中可以更方便的控制&#xff0c;减少暴露的风险 Secret&#xff1a;保存加密的信息 2、Secret类型&#xff1a; docker-registry&am…

第十二章 Java内存模型与线程(二)

文章目录 12.4 Java与线程12.4.1 线程的实现12.4.2 Java线程调度12.4.3 状态转换 12.5 Java与协程12.5.1 内核线程的局限12.5.2 协程的复苏12.5.3 Java的解决方案 12.4 Java与线程 12.4.1 线程的实现 实现线程主要有三种方式&#xff1a;使用内核线程实现&#xff08;1&#…

算法通关村第十六关—滑动窗口与堆结合(黄金)

滑动窗口与堆结合 堆与滑动窗口问题的结合 LeetCode239给你一个整数数组nums,有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位&#xff0c;返回滑动窗口中的最大值。  对于最大值、K个最大这种场…

【教3妹学编程-算法题】最大频率元素计数

2哥 : 3妹&#xff0c;最近有个电视剧《繁花》非常火&#x1f525;&#xff0c;你听说了吗&#xff1f; 3妹&#xff1a;没有&#xff0c;最近一直在忙着找工作&#xff0c;哪有时间看电视啊 2哥 : 啊&#xff1f;大周末还不休息一下啊&#xff0c;这么辛苦。 3妹&#xff1a;当…

压力测试JMeter

一、JMeter概述 Apache JMeter是100%纯JAVA桌面应用程序&#xff0c;被设计为用于测试客户端/服务端结构的软件(例如web应用程序)。它可以用来测试静态和动态资源的性能&#xff0c;例如&#xff1a;静态文件&#xff0c;Java Servlet,CGI Scripts,Java Object,数据库和FTP服务…

k8s node节点加入集群,token过期

1、master01节点执行 kubeadm token create --print-join-command 2、执行命令 kubeadm join 192.168.0.236:16443 --token qucd8q.hsfq4a1afluzaky3 --discovery-token-ca-cert-hash sha256:92175a356db070deb2ddd3823e288e3005a4baeec9b68580dcc11ce4d3767195 3、查看node02…

FPGA节省资源篇------正确处理设计优先级

声明&#xff1a;以下文章来源于孤独的单刀&#xff0c;仅供学习用途 概述 假如现在有一种方法–可以在不怎么需要修改已有设计的情况下&#xff0c;就可以帮您节省50%的设计资源&#xff0c;那你会试试看吗&#xff1f; 当前市场环境下&#xff0c;更低廉的成本却可获得同等…

steam游戏搬砖项目还能火多久?

最近放假回到老家&#xff0c;见了不少亲戚朋友&#xff0c;大家不约而同都在感叹今年大环境不好&#xff0c;工作不顺&#xff0c;生意效益不好&#xff0c;公司状况不佳&#xff0c;反问我们生意如何&#xff1f;为了让他们心里好受一点&#xff0c;我也假装附和道:也不咋地&…

3000多个厂商默认帐号、默认密码

做网工这行&#xff0c;多少都会遇上各种各样的厂商设备&#xff0c;遇上一些新设备&#xff0c;虽然没有更改密码&#xff0c;但不知道初始默认账号和密码是啥。 今天就给你整理了一波&#xff0c;三千多个厂商默认帐号、默认密码&#xff0c;方便你查阅。 不过&#xff0c;…

自创C++题目——风扇

预估难度 简单 题目描述 有一个风扇&#xff0c;它有个旋转叶片&#xff0c;每个旋转叶片的编号是&#xff0c;请输出它旋转后&#xff0c;中心点与地面的直线距离哪个叶片最近&#xff0c;输出此旋转叶片的编号。默认以“”的形式。 当时&#xff1a; 当或时&#xff0c;…

MATLAB二维与三维绘图实验

本文MATLAB源码&#xff0c;下载后直接打开运行即可[点击跳转下载]-附实验报告https://download.csdn.net/download/Coin_Collecter/88740747 一、实验目的 掌握图形对象属性的基本操作。掌握利用图形对象进行绘图操作的方法。 二、实验内容 利用图形对象绘制曲线&#xff…

Java基础 - 黑马

我是南城余&#xff01;阿里云开发者平台专家博士证书获得者&#xff01; 欢迎关注我的博客&#xff01;一同成长&#xff01; 一名从事运维开发的worker&#xff0c;记录分享学习。 专注于AI&#xff0c;运维开发&#xff0c;windows Linux 系统领域的分享&#xff01; 知…

最佳实践分享:SQL性能调优

SQL性能调优是一个需要不断探索和实践的过程&#xff0c;旨在确保数据库查询的高效运行。本文将分享一些SQL性能调优的最佳实践&#xff0c;帮助您提升数据库性能&#xff0c;减少查询响应时间。 一、索引优化 索引是提高查询性能的关键。以下是一些关于索引优化的建议&#…

完全备份、增量备份、差异备份、binlog日志

1 案例1&#xff1a;完全备份与恢复 1.1 问题 练习物理备份与恢复练习mysqldump备份与恢复 1.2 方案 在数据库服务器192.168.88.50 练习数据的备份与恢复 1.3 步骤 实现此案例需要按照如下步骤进行。 步骤一&#xff1a;练习物理备份与恢复 冷备份&#xff0c;需停止数…

数据结构第十四弹---链式二叉树基本操作(下)

链式二叉树 1、翻转二叉树2、判断两棵树是否相同3、判断二叉树是否是单值二叉树4、对称二叉树5、判断二叉树是否是平衡二叉树6、判断二叉树是否是另一棵二叉树的子树7、二叉树的销毁8、二叉树的深度遍历8.1、前序遍历8.2、中序遍历8.3、后序遍历 9、二叉树的构造和遍历总结 1、…

Java中的JVM指令和Arthas以及Dump文件(jvisualvm和MemoryAnalyzer工具)整体分析

前言 前天线上服务器突然内存和CPU都爆掉了&#xff0c;两者都处于一种高负载的状态&#xff0c;而且还是周末的情况下&#xff0c;起初运维同事怀疑是用户数量暴增&#xff0c;但是数据面板上并没有出现很大的暴增现象&#xff0c;之前的服务器4G的内存都跑不满后面升到8G还是…

NFS网络共享服务存储

目录 一、NFS简介 1、NFS定义&#xff1a; 2、NFS的特点 3、NFS的优缺点 4、NFS的原理图示 二、服务端NFS配置文件&#xff1a;/etc/exports 三、实验&#xff1a;NFS共享存储服务配置 1、服务端安装nfs-utils与rpcbind软件包 2、服务端新建共享文件夹目录并赋予权限 …

【数据库】sql优化有哪些?从query层面和数据库层面分析

目录 归纳sql本身的优化数据库层面的优化 归纳 这类型问题可以称为&#xff1a;Query Optimization&#xff0c;从清华AI4DB的paper list中&#xff0c;该类问题大致可以分为&#xff1a; Query RewriterCardinality EstimationCost EstimationPlan Optimization 从中文的角…

排序算法9----计数排序(C)

计数排序是一种非比较排序&#xff0c;不比较大小 。 1、思想 计数排序又称为鸽巢原理&#xff0c;是对哈希直接定址法的变形应用。 2、步骤 1、统计数据&#xff1a;统计每个数据出现了多少次。&#xff08;建立一个count数组&#xff0c;范围从[MIN,MAX],MAX代表arr中…