文档章节

归并排序及几个常用排序比较

o
 osc_g8254g7s
发布于 2019/08/19 20:31
字数 1029
阅读 16
收藏 0

精选30+云产品,助力企业轻松上云!>>>

 1 void merge(int arr[], int l, int m,int r)
 2 {
 3     int i = 0, j = 0, k =l;
 4     int n1 = m - l + 1;        //左边步长
 5     int n2 = r - m;            //右边步长
 6     std::vector<int> vec_l(&arr[l], &arr[m+1]);
 7     std::vector<int> vec_r(&arr[m+1], &arr[r+1]);
 8     while (i < n1&&j < n2)
 9     {
10         if (vec_l[i] <= vec_r[j])
11         {
12             arr[k] = vec_l[i];
13             i++;
14         }
15         else
16         {
17             arr[k] = vec_r[j];
18             j++;
19         }
20         k++;
21     }
22         while (i<n1)
23         {
24             arr[k]= vec_l[i];
25             i++;
26             k++;
27         }
28 
29         while (j<n2)
30         {
31             arr[k] = vec_r[j];
32             j++;
33             k++;
34         }
35     
36 
37 }
38 
39 void mergeSort(int arr[], int l, int r)
40 {
41     if (l < r)
42     {
43         int m = l + (r - l) / 2;
44 
45         mergeSort(arr, l, m);
46         mergeSort(arr, m + 1, r);
47 
48         merge(arr, l, m, r);
49     }
50 }

再贴张排序的时间与空间复杂度的图

总结: 

为什么堆排序的时间复杂度理想却很少被采用:

作者:qinzp
链接:https://www.zhihu.com/question/23873747/answer/327295185
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
-------------------------------------------------------------------
堆排序下,数据读取的开销变大。在计算机进行运算的时候,数据不一定会从内存读取出来,而是从一种叫cache的存储单位读取。原因是cache相比内存,读取速度非常快,所以cache会把一部分我们经常读取的数据暂时储存起来,以便下一次读取的时候,可以不必跑到内存去读,而是直接在cache里面找。
一般认为读取数据遵从两个原则:temporal locality,也就是不久前读取过的一个数据,在之后很可能还会被读取一遍;另一个叫spatial locality,也就是说读取一个数据,在它周围内存地址存储的数据也很有可能被读取到。因此,在读取一个单位的数据(比如1个word)之后,不光单个word会被存入cache,与之内存地址相邻的几个word,都会以一个block为单位存入cache中。另外,cache相比内存小得多,当cache满了之后,会将旧的数据剔除,将新的数据覆盖上去。
在进行堆排序的过程中,由于我们要比较一个数组前一半和后一半的数字的大小,而当数组比较长的时候,这前一半和后一半的数据相隔比较远,这就导致了经常在cache里面找不到要读取的数据,需要从内存中读出来,而当cache满了之后,以前读取的数据又要被剔除。
简而言之快排和堆排读取arr[i]这个元素的平均时间是不一样的。
 
----------------------------------------------------------------------
快速排序最优的情况就是每一次取到的元素都刚好平分整个数组,最优的情况下时间复杂度为:O( nlogn )

  最差的情况就是每一次取到的元素就是数组中最小/最大的,这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序),快速排序最差的情况下时间复杂度为:O( n^2 )

     最优的情况下空间复杂度为:O(logn)  ;每一次都平分数组的情况
     最差的情况下空间复杂度为:O( n )      ;退化为冒泡排序的情况(用来存储哨兵变量的临时值)
----------------------------------------------------------------------------

快排数据越无序越快(加入随机化后基本不会退化),平均常数最小,不需要额外空间,不稳定排序。
归排速度稳定,常数比快排略大,需要额外空间(还有个东西叫多路归并),稳定排序。(归并排序需要额外空间记录子数组的值)

------------------------------------------------------------------------

实际问题中归并排序并不比快排应用少。快排需要递归,就这一点基就可以在许多大数据应用场景把它枪毙了。而归并排序的scale能力比快排好很多,可以分布式处理,其实很受欢迎的

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
数据结构与算法系列十四(归并排序)

1.引子 1.1.为什么要学习数据结构与算法? 有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀! 有人说,我是做业务开发的,只要熟练API...

yhhitall
04/14
13
0
【转】常用排序算法的性能分析及应用场景

一.排序算法分类 1.插入排序法 直接插入排序,希尔排序(面试最常问) 2.交换排序 冒泡排序,快速排序(面试最常问) 3.选择排序 直接选择排序,堆排序(面试最常问) 4.归并排序 归并排序 ...

osc_41dppmun
2018/06/28
7
0
算法基础 - 排序

上半年换工作后变懒散了,好久没更新了,最近在读道长写的《iOS 面试之道》这本书的算法部分,可以在小专栏上阅读电子书,也可以在京东上购买实体书,写这篇文章文章记录一下常用的算法知识。...

_誌念
2018/09/04
0
0
归并排序:步骤讲解与代码实现

归并排序   在一些常用的排序中,归并排序在时间开销上来说可以是排序中的最佳实践之一(时间复杂度=n*log n),今天我们就来看看归并是如何实现的。   归并排序大致可以分为两步:   ...

宇的季节
2017/09/10
0
0
归并排序:步骤讲解与代码实现

归并排序   在一些常用的排序中,归并排序在时间开销上来说可以是排序中的最佳实践之一(时间复杂度=n*log n),今天我们就来看看归并是如何实现的。   归并排序大致可以分为两步:   ...

宇的季节
2017/09/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Buffer的创建及使用源码分析——ByteBuffer为例

目录 Buffer概述 Buffer的创建 Buffer的使用 总结 参考资料 Buffer概述 注:全文以ByteBuffer类为例说明 在Java中提供了7种类型的Buffer,每一种类型的Buffer根据分配内存的方式不同又可以分为...

osc_zoa046qb
13分钟前
11
0
《 ZooKeeper : Wait-free coordination for Internet-scale systems 》论文研读

Zookeeper 研读 说明:本文为论文 《 ZooKeeper : Wait-free coordination for Internet-scale systems 》 的个人理解,难免有理解不到位之处,欢迎交流与指正 。 论文地址:Zookeeper Paper...

osc_4isxawz4
13分钟前
8
0
利用__new__实现单例模式

26 利用__new__实现单例模式 python当中有很多方法都可以实现单例模式, 但利用__new__无疑是最推荐的方式. 代码如下: class Demo:is_instance = Nonedef __new__(cls, *args, **kwargs...

_Change_
15分钟前
4
0
如何白嫖微软Azure12个月及避坑指南

Azure是微软提供的一个云服务平台。是全球除了AWS外最大的云服务提供商。Azure是微软除了windows之外另外一个王牌,微软错过了移动端,还好抓住了云服务。这里的Azure是Azure国际不是Azure中...

osc_dwuu5jqk
15分钟前
0
0
Mybatis源码初探——优雅精良的骨架

@ 目录 前言 精良的Mybatis骨架 宏观设计 基础支撑 日志 日志的加载 日志的使用 数据源 数据源的创建 池化技术原理 数据结构 获取连接 回收连接 缓存 缓存的实现 CacheKey 反射 总结 前言 My...

osc_r9wwwi0j
16分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部