文档章节

常用排序方法

baihan
 baihan
发布于 2013/10/14 02:03
字数 1311
阅读 21
收藏 1
点赞 0
评论 0

1 快速排序(QuickSort)


快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。


(1) 如果不多于1个数据,直接返回。


(2) 一般选择序列最左边的值作为支点数据。


(3) 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。


(4) 对两边利用递归排序数列。


快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。


2 归并排序(MergeSort)


归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。


3 堆排序(HeapSort)


堆排序适合于数据量非常大的场合(百万数据)。


堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。


堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。


4 Shell排序(ShellSort)


Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。


Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。


5 插入排序(InsertSort)


插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。


6 冒泡排序(BubbleSort)


冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。


7 交换排序(ExchangeSort)和选择排序(SelectSort)


这两种排序方法都是交换方法的排序算法,效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。


8 基数排序(RadixSort)


基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。


9 总结


下面是一个总的表格,大致总结了我们常见的所有的排序算法的特点。 


排序法 平均时间 最差情形 稳定度 额外空间 备注 
冒泡 O(n2)     O(n2) 稳定 O(1) n小时较好 
交换     O(n2)     O(n2) 不稳定 O(1) n小时较好 
选择 O(n2) O(n2) 不稳定 O(1) n小时较好 
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好 
基数 O(logRB) O(logRB) 稳定 O(n) 
B是真数(0-9),


R是基数(个十百)
 
Shell O(nlogn) O(ns) 1<s<2 不稳定 O(1) s是所选分组 
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好 
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好 
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好

本文转载自:

共有 人打赏支持
baihan
粉丝 1
博文 12
码字总数 2584
作品 0
深圳
高级程序员
Java程序员的日常—— Arrays工具类的使用

这个类在日常的开发中,还是非常常用的。今天就总结一下Arrays工具类的常用方法。最常用的就是asList,sort,toStream,equals,copyOf了。另外可以深入学习下Arrays的排序算法,这个还是非常有用...

青夜之衫
2017/12/05
0
0
学习笔记(10月26日)--复习&练习

二周四次课(10月26日) 复习,做如下练习题 1.实现1-100的所有的和 sum = 0for n in xrange(1, 101): sum += n n += 1print('1+2+3+...+100 = ' + str(sum)) 结果: 1+2+3+...+100 = 5050 2......

wanyang_wanyang
07/03
0
0
排序——排序的基本概念

一、排序概念 排序是将一组数据按递增或递减的顺序排列。排序是最一种最基础的、最常用的算法。 二、排序的分类 在计算机中,由于数据形式、数量和保存形式不同,对数据进行排序的方法也不同...

翼动动空
2016/06/02
4.5K
0
Learning to rank基本算法小结

我知道你们都是看题图进来的!!! 最近工作中需要调研一下搜索排序相关的方法,这里写一篇水文,总结一下几天下来的调研成果。包括 Learning to rank 基本方法 Learning to rank 指标介绍 ...

felix
2017/04/24
0
0
PHP常用数组函数小结

1.requesturi获取到最后的元素indextest1test2test3(一般框架的的路由路径就是这样的) $requesturi ="index\test1\test2\test3";$arr=explode("",$request_uri);$moudle = array_shift($ar......

熊猫88
2016/01/06
58
0
白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇

在我的博客对冒泡排序,直接插入排序,直接选择排序,希尔排序,归并排序,快速排序和堆排序这七种常用的排序方法进行了详细的讲解,并做成了电子书以供大家下载。下载地址为:http://downlo...

长平狐
2012/12/10
53
0
NSDictionary / NSMutableDictionary 及 NSArray / ...

NSDictionary 常用方法总结 +(id)dictionaryWithObjectsAndKeys:obj1,key1,obj2,key2,......nil 顺序添加对象和键值来创建一个字典,注意结尾是nil -(id)initWithObjectsAndKeys::obj1,key1,......

mahb520
2012/11/20
0
0
第12条 深虑实现Comparable接口

Comparable接口,此接口强行对实现它的每个类的对象进行整体排序。此排序被称为该类的自然排序 ,类的 compareTo 方法被称为它的自然比较方法 。实现此接口的对象列表(和数组)可以通过 Co...

李白吃白菜
2016/04/11
49
0
python之pandas的基本使用(2)

续 python之pandas模块的基本使用(1) 一、排序和排名 排序:sortindex和sortvalues函数 代码示例: 排名:根据值的大小/出现次数来进行排名,得到一组排名值:rank函数 二、索引重复的情况...

cxmscb
2017/01/22
0
0
JavaScript实现常用的排序算法

▓▓▓▓▓▓ 大致介绍   由于最近要考试复习,所以学习js的时间少了 -_-||,考试完还会继续的努力学习,这次用原生的JavaScript实现以前学习的常用的排序算法,有冒泡排序、快速排序、直接...

胡壮壮
2017/05/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

spring-@RequestBody

@RequestMapping("/login")    public void login(@RequestBody String userName,@RequestBody String pwd){      System.out.println(userName+" :"+pwd);    }    ......

说回答
5分钟前
0
0
Redis安装

大家可以通过该链接获取安装详情(这是一个Word文档,支持下载): http://note.youdao.com/noteshare?id=7a327ed6c58fb2037ba537e58ecf7510&sub=480DB8EF349747C3983B73AE94D45BB1 其他参考...

一梦心草
6分钟前
0
0
MySQL按天,按周,按月,按时间段统计【转载】

https://blog.csdn.net/qq_28056641/article/details/78306870 select DATE_FORMAT(create_time,'%Y%m%d') days,count(caseid) count from tc_case group by days; select DATE_FORMAT(creat......

李道福
7分钟前
0
0
浅谈parallelStream

parallelStream是什么,它是一个集合的并发处理流.其作用是把一个集合中的数据分片,进行一个多线程的处理,增快运行速度. 比如说这样一段代码 private Set<SysRole> sysRoles;private Set<St...

算法之名
9分钟前
3
0
器者,道之所载

形而上者谓之道,形而下者谓之器,化而裁之谓之变;推而行之谓之通,举而措之天下之民,谓之事业。—— 《道德经》

了凡川
11分钟前
0
0
C#命名规范中文版/C#编码规范中文版

最新文档地址https://github.com/hiramtan/CSharpNamingGuidelines_Chinese C#命名规范中文版/C#编码规范中文版 示例 /*****************************************************************......

海贝Hibey
12分钟前
0
0
刚从eclipse转到Intellij IDEA,分享一些配置经验

刚从eclipse转到Intellij IDEA,分享一些配置经验,IntelliJ IDEA作为最好的Java开发工具,在智能代码助手、代码自动提示、重构、J2EE支持、Ant、JUnit、CVS整合、代码审查、 创新的GUI设计等...

舒文joven
14分钟前
1
0
lombok 引入后,测试类始终找不到get,set方法。

开发环境为idea,jdk1.7,maven3.5. 网上直接搜出来的方法有: 1、在setting里安装lombok的plugins; 2、如下图,勾选enable annocation processing选项 3、升级maven plugins插件 我尝试了以...

Kidult
20分钟前
0
0
Duang,HUAWEI DevEco IDE全面升级啦

想感受全新UI带来的视觉及交互体验、 HiKey970开发板调测、 HiAI API推荐和收藏、 深度AI模型分析等新功能, 体验高清晰度和流畅度的远程AI真机调测吗? 全新的UI设计 采用最优秀的视觉及交互...

华为终端开放实验室
28分钟前
1
0
阻止事件冒泡,阻止默认事件

1.event.stopPropagation()方法 这是阻止事件的冒泡方法,不让事件向documen上蔓延,但是默认事件任然会执行,当你掉用这个方法的时候,如果点击一个连接,这个连接仍然会被打开, 2.event....

闫亚亚
30分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部