【重温经典算法之一】归并排序
发布日期:2021-09-05 08:11:44 浏览次数:4 分类:技术文章

本文共 2216 字,大约阅读时间需要 7 分钟。

     归并排序的基本思想是分治法,先将要排序的数组从中间分成两个小的数组,然后分别排序这两个小的数组,最后将这两个小的已经排序的数组合并成一个有序的数组。所以归并排序的基本框架为:

1 MergeSort(array, start, end) 2 { 3    if (start < end) 4    { 5        mid = (start + end) / 2; 6        MergeSort(array, start, mid);  //递归排序左边的数组 7        MergeSort(array, mid + 1, end);  //递归排序右边的数组 8        MergeArray(array, start, mid, end);  //合并两个已经排序的相邻数组 9    }10 }

     有了上面的框架,归并排序就转换为将两个已经排序的数组合并为一个大的排序数组问题。这个非常简单,只要先比较二个数组的第一个数,谁小就先取谁,取了后就在对应数组中删除这个数。然后再进行比较,如果有数组为空,那直接将另一个数组的数据依次取出即可。

1 void MergeArray(int data[], int start, int mid, int end, int temp[]) 2 { 3     int i = start, j = mid + 1, k = start; 4  5     while (i <= mid && j <= end) 6     { 7         if (data[i] <= data[j]) 8             temp[k++] = data[i++]; 9         else10             temp[k++] = data[j++];11     } 12     while (i <= mid)13         temp[k++] = data[i++];14     while (j <= end)15         temp[k++] = data[j++];16     for (k = start; k <= end; k++)17         data[k] = temp[k];18 }

     归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程,时间复杂度可以记为O(N),故一共为O(N*logN)。因为归并排序每次都是在相邻的数据中进行操作,所以归并排序在复杂度为O(N*logN)的几种排序方法(快速排序,归并排序,希尔排序,堆排序)中效率算是比较高的。

1 void MergeArray(int data[], int start, int mid, int end, int temp[]) 2 { 3     int i = start, j = mid + 1, k = start; 4  5     while (i <= mid && j <= end) 6     { 7         if (data[i] <= data[j]) 8             temp[k++] = data[i++]; 9         else10             temp[k++] = data[j++];11     } 12     while (i <= mid)13         temp[k++] = data[i++];14     while (j <= end)15         temp[k++] = data[j++];16     for (k = start; k <= end; k++)17         data[k] = temp[k];18 }19 void MergeSortRecursively(int data[], int start, int end, int temp[])20 {21     if (start == end)22         return;23 24     int mid = (start + end) / 2;25     MergeSortRecursively(data, start, mid, temp); //左边的排序26     MergeSortRecursively(data, mid + 1, end, temp);  //右边的排序27     MergeArray(data, start, mid, end, temp);28 }29 void MergeSort(int data[], int n)30 {31     if (data == NULL || n < 2)32         return;33     int *temp = new int[n];34     MergeSortRecursively(data, 0, n - 1, temp);35     delete [] temp;36 }
View Code

  下面是我在自己电脑上测试了下归并排序和qsort排序的效率:

  对20000个随机数据进行测试:

  对200000个随机数据进行测试:

转载地址:https://blog.csdn.net/weixin_34235135/article/details/85605878 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:asp.net 从客户端中检测到有潜在危险的 Request.Form 值错误解
下一篇:修改ViewPager调用setCurrentItem时,滑屏的速度

发表评论

最新留言

很好
[***.229.124.182]2024年03月07日 17时17分42秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle里面如何查询sqlid,CSS_oracle中如何查看sql, --查询表状态:  select uo.O - phpStudy... 2019-04-21
oracle 查询中用case,oracle case when 在查询时候的用法。 2019-04-21
oracle正在运行的程序包,ORACLE PL/SQL编程详解之程序包的创建与应用 2019-04-21
php局部页面滚动,在访问另一页面后保留浏览器滚动位置 - php 2019-04-21
jmeter运行linux命令行,Jmeter在linux上运行(命令行运行Jmeter) 2019-04-21
linux服务器怎么添加站点,如何增加站点或虚拟主机及文件说明 2019-04-21
linux系统输入指令,Linux系统基础 - 基本操作命令 2019-04-21
linux设备管理命令,Linux命令(设备管理).doc 2019-04-21
linux 中文utf-8转gbk编码,Linux平台下 GBK编码转UTF-8编码 2019-04-21
linux安装软件在boot,在Linux系统上安装Spring boot应用的教程详解 2019-04-21
linux进入用户user1主目录,Linux系统命令提示符为[user1@localhost root]当前用户所在目录为( )... 2019-04-21
取消linux自动登录,linuxdeepin 如何取消自动登录啊? 2019-04-21
linux线程存储,Linux系统编程手册:线程:线程安全和每线程存储 2019-04-21
linux以root账号登陆gnome,CentOS 7 - 以root身份登入Gnome 2019-04-21
linux crontab 备份数据库 空文件,Linux下使用crontab自动备份数据库 2019-04-21
linux批处理模式,巧用linux-top的批处理模式 2019-04-21
linux信号量机制例题,第二章 信号量机制及几个经典例题 2019-04-21
linux ba 模拟,在你的 Python 游戏中模拟引力 | Linux 中国 2019-04-21
c语言表达式3649的值是,535个C语言经典实例目录.doc 2019-04-21
c语言Wndproc未定义,小弟我用c语言写了一个windows窗口,为什么有提示未定义的变量类型... 2019-04-21