各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。

排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相同项的相对位置有没有发生变化,如果没有发生变化,即该排序方法是稳定的,如果发生变化,则说明该排序方法是不稳定的。

如果记录中关键字不能重复,则排序结果是唯一的,那么选择的排序方法稳定与否就无关紧要了;如果关键字可以重复,则在选择排序方法时,就要根据具体的需求来考虑选择稳定还是不稳定的排序方法。那么,哪些排序算法是不稳定的呢?

“快些选堆”:其中“快”指快速排序,“些”指希尔排序,“选”指选择排序,“堆”指堆排序,即这四种排序方法是不稳定的,其他自然都是稳定的。

排序算法分类

1、插入类排序

即在一个已经有序的序列中,插入一个新的记录,就好比军训排队,已经排好一个纵队,这时来了个新家伙,于是新来的“插入”这个队伍中的合适位置。这类排序有:直接插入排序、折半插入排序、希尔排序。

2、交换类排序

该类方法的核心是“交换”,即每趟排序,都是通过一系列的“交换”动作完成的,如军训排队时,教官说:你比旁边的高,你俩交换下,还比下一个高就继续交换。这类排序有:冒泡排序、快速排序。

3、选择类排序

该方法的核心是“选择”,即每趟排序都选出一个最小(或最大)的记录,把它和序列中的第一个(或最后一个)记录交换,这样最小(或最大)的记录到位。如军训排队时,教官选出个子最小的同学,让他和第一个位置的同学交换,剩下的继续选择。这类排序有:选择排序、堆排序。

4、归并类排序

所谓归并,就是将两个或两个以上的有序序列合并成一个新的有序序列。如军训排队时,教官说:每个人先和旁边的人组成二人组,组内排好队,二人组和旁边的二人组组成四人组,内部再排好队,以此类推,直到最后全部同学都归并到一个组中并排好序。这类排序有:(二路)归并排序。

5、基数类排序

此类方法较为特别,是基于多关键字排序的思想,把一个逻辑关键字拆分成多个关键字,如一副扑克牌,按照基数排序思想可以先按花色排序,则分成4堆,每堆再按A-K的顺序排序,使得整副扑克牌最终有序。

排序算法分析

本文主要分析的排序算法有:冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。

交换算法

由于大部分排序算法中使用到两个记录相互交换的动作,因此将交换动作单独封装出来,便于各排序算法使用。

插入排序

算法思想:每趟将一个待排序的关键字,按照其关键字值的大小插入到已经排好的部分序列的适当位置上,直到插入完成。

算法性能:在内层循环中this[j]=this[j-1],这句是作为基本操作。考虑最坏情况,即整个序列是逆序的,则其基本操作总的执行次数为n*(n-1)/2,其时间复杂度为O(n*n)。考虑最好情况,即整个序列已经有序,则循环内的操作均为常量级,其时间复杂度为O(n)。因此本算法平均时间复杂度为O(n*n)。算法所需的额外空间只有一个value,因此空间复杂度为O(1)。

希尔排序

算法思想:希尔排序又叫做缩小增量排序,是将待排序的序列按某种规则分成几个子序列,分别对这几个子序列进行插入排序,其中这一规则就是增量。如可以使用增量5、3、1来分格序列,且每一趟希尔排序的增量都是逐渐缩小的,希尔排序的每趟排序都会使得整个序列变得更加有序,等整个序列基本有序了,再使用一趟插入排序,这样会更有效率,这就是希尔排序的思想。

算法性能:希尔排序的时间复杂度平均情况为O(nlogn),空间复杂度为O(1)。希尔排序的增量取法要注意,首先增量序列的最后一个值一定是1,其次增量序列中的值没有除1之外的公因子,如8,4,2,1这样的序列就不要取(有公因子2)。

冒泡排序

算法思想:通过一系列的“交换”动作完成的,首先第一个记录与第二个记录比较,如果第一个大,则二者交换,否则不交换;然后第二个记录和第三个记录比较,如果第二个大,则二者交换,否则不交换,以此类推,最终最大的那个记录被交换到了最后,一趟冒泡排序完成。在这个过程中,大的记录就像一块石头一样沉底,小的记录逐渐向上浮动。冒泡排序算法结束的条件是一趟排序没有发生元素交换。

算法性能:最内层循环的元素交换操作是算法的基本操作。最坏情况,待排序列逆序,则基本操作的总执行次数为(n-1+1)*(n-1)/2=n(n-1)/2,其时间复杂度为O(n*n);最好情况,待排序列有序,则时间复杂度为O(n),因此平均情况下的时间复杂度为O(n*n)。算法的额外辅助空间只有一个用于交换的temp,所以空间复杂度为O(1)。

快速排序

算法思想:以军训排队为例,教官说以第一个同学为中心,比他矮的站他左边,比他高的站他右边,这就是一趟快速排序。因此,一趟快速排序是以一个枢轴,将序列分成两部分,枢轴的一边比它小(或小于等于),另一边比它大(或大于等于)。

算法性能:快速排序最好情况下时间复杂度为O(nlogn),待排序列越接近无序,则该算法效率越高,在最坏情况下时间复杂度为O(n*n),待排序列越接近有序,则该算法效率越低,算法的平均时间复杂度为O(nlogn)。就平均时间而言,快速排序是所有排序算法中最好的。该算法的空间复杂度为O(logn),快速排序是递归进行的,需要栈的辅助,因此需要的辅助空间比前面几类排序方法要多。

快速排序的效率和选取的“枢轴”有关,选取的枢轴越接近中间值,算法效率就越高,因此为了提高算法效率,可以在第一次选取“枢轴”时做文章,如在数据堆中随机选取3个值,取3个值的平均值作为“枢轴”,就如抽样一般。关于具体如何提高快速排序算法的效率,在本文不做详细介绍了,点到为止。(感兴趣的读者可以自行去研究)

选择排序

算法思想:该算法的主要动作就是“选择”,采用简单的选择方式,从头至尾顺序扫描序列,找出最小的一个记录,和第一个记录交换,接着从剩下的记录中继续这种选择和交换,最终使序列有序。

算法性能:将最内层循环中的比较视为基本操作,其执行次数为(n-1+1)*(n-1)/2=n(n-1)/2,其时间复杂度为O(n*n),本算法的额外空间只有一个temp,因此空间复杂度为O(1)。

堆排序

算法思想:堆是一种数据结构,最好的理解堆的方式就是把堆看成一棵完全二叉树,这个完全二叉树满足任何一个非叶节点的值,都不大于(或不小于)其左右孩子节点的值。若父亲大孩子小,则这样的堆叫做大顶堆;若父亲小孩子大,这样的堆叫做小顶堆。根据堆的定义,其根节点的值是最大(或最小),因此将一个无序序列调整为一个堆,就可以找出这个序列的最大(或最小)值,然后将找出的这个值交换到序列的最后(或最前),这样有序序列元素增加1个,无序序列中元素减少1个,对新的无序序列重复这样的操作,就实现了序列排序。堆排序中最关键的操作是将序列调整为堆,整个排序的过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树的过程。

堆排序执行过程(大顶堆):

(1)从无序序列所确定的完全二叉树的第一个非叶子节点开始,从右至左,从下至上,对每个节点进行调整,最终将得到一个大顶堆。将当前节点(a)的值与其孩子节点进行比较,如果存在大于a值的孩子节点,则从中选出最大的一个与a交换。当a来到下一层的时候重复上述过程,直到a的孩子节点值都小于a的值为止。

(2)将当前无序序列中第一个元素,在树中是根节点(a)与无序序列中最后一个元素(b)交换。a进入有序序列,到达最终位置,无序序列中元素减少1个,有序序列中元素增加1个,此时只有节点b可能不满足堆的定义,对其进行调整。

(3)重复过程2,直到无序序列中的元素剩下1个时排序结束。

算法性能:完全二叉树的高度为[log(n+1)],即对每个节点调整的时间复杂度为O(logn),基本操作总次数是两个并列循环中基本操作次数相加,则整个算法时间复杂度为O(logn)*n/2+O(logn)*(n-1),即O(nlogn)。额外空间只有一个temp,因此空间复杂度为O(1)。

堆排序的优点是适合记录数很多的场景,如从1000000个记录中选出前10个最小的,这种情况用堆排序最好,如果记录数较少,则不提倡使用堆排序。另外,Hash表+堆排序是处理海量数据的绝佳组合,关于海量数据处理会在之后的博文中介绍到。

归并排序

算法思想:其核心就是“两两归并”,首先将原始序列看成每个只含有单独1个元素的子序列,两两归并,形成若干有序二元组,则第一趟归并排序结束,再将这个序列看成若干个二元组子序列,继续两两归并,形成若干有序四元组,则第二趟归并排序结束,以此类推,最后只有两个子序列,再进行一次归并,即完成整个归并排序。

原文发布于微信公众号 - 顶级程序员(TopCoding)

原文发表时间:2016-10-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复...

571
来自专栏magicsoar

Effective Modern C++翻译(2)-条款1:明白模板类型推导

第一章 类型推导 C++98有一套单一的类型推导的规则:用来推导函数模板,C++11轻微的修改了这些规则并且增加了两个,一个用于auto,一个用于decltyp...

19010
来自专栏数据结构与算法

P3709 大爷的字符串题(50分)

题目背景 在那遥远的西南有一所学校 /*被和谐部分*/ 然后去参加该省省选虐场 然后某蒟蒻不会做,所以也出了一个字符串题: 题目描述 给你一个字符串a,每次询问...

3457
来自专栏ACM算法日常

基础算法|7 希尔排序 HDU 1425

我们从最初的冒泡排序算法,到上篇文章的折半插入排序算法,我们一共学习了5种排序算法,相信以大家的聪明才智肯定都消化了^_^。在本篇文章中,我们又将学习第6种排序...

922
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之 适合大规模的数据排序 数据结构与算法学习笔记之如何分析一个排序算法?

在数据排序的算法中,不同数据规模应当使用合适的排序算法才能达到最好的效果,如小规模的数据排序,可以使用冒泡排序、插入排序,选择排序,他们的时间复杂度都为O(n...

934
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

2556
来自专栏zaking's

用js来实现那些数据结构03(数组篇03-排序及多维数组)

  终于,这是有关于数组的最后一篇,下一篇会真真切切给大家带来数据结构在js中的实现方式。那么这篇文章还是得啰嗦一下数组的相关知识,因为数组真的太重要了!不要怀...

3545
来自专栏Web项目聚集地

面试前你必须知道的三个排序算法

今天分享的是三种排序算法,在面试、实际编程中经常会碰到和使用到的,我会带领大家从分析排序算法技巧上以及代码实现上全面理解这一知识点的掌握。

1452
来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法

Java常用排序算法/程序员必须掌握的8大排序算法 分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排...

5078
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

37211

扫码关注云+社区

领取腾讯云代金券