专栏首页顶级程序员各大排序算法性能比较及演示实例

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

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

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

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

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

排序算法分类

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)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 与围棋相比,公众会认为五子棋更简单,根本原因是什么?

    围棋要布局下完数子,五子棋连五就结束了,耗时和用子都是围棋多的多,大众觉得围棋更复杂也不奇怪。 也有人回答数学上说,围棋就比五子棋复杂的,没说到点上去。因为穷...

    顶级程序员
  • 人工智能“鉴黄师”

    最近,雅虎利用分类神经网络搭建了一套可以辨别Not Suitable for Work(上班不宜,以下简称NSFW)色情图片的Caffe模型,并将源码搬上了gi...

    顶级程序员
  • 学霸用SCI论文求婚!网友:这波高级狗粮我吃!

    来源:福建共青团 最近,一部很火的剧《你好旧时光》在全网热播,主角余周周和林杨上演了学霸情侣的青春成长故事。 ? 有人是学霸,有人擅长秀恩爱, 但有人不仅是学...

    顶级程序员
  • 排序算法

    选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

    lwen
  • 算法之旅 | 冒泡排序法

    HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

    HTML5学堂
  • 不稳定的原地排序算法:选择排序

    在之前的文章中,我们说了两个原地排序算法:插入排序和冒泡排序。分析两个算法的原理,也用代码实现了两个算法。最后,我们也从两个算法入手,引出了评价算法性能的两个重...

    飞翔的竹蜻蜓
  • 经典排序算法详细介绍

    渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    IT茂茂
  • 排序算法(九):桶排序

    桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中...

    zhipingChen
  • 算法一看就懂之「 排序算法 」

    之前的文章咱们已经聊过了「 数组和链表 」、「 堆栈 」、「 队列 」和「 递归 」,这些要么是基础的数据结构,要么就是巧妙的编程方法。从今天起咱们来进入真正的...

    奎哥
  • 【漫画】为什么说O(n)复杂度的基数排序没有快速排序快?

    老大:我简单给你讲下吧,你学过那么多排序,估计一看就懂了。基数排序,是一种基数“桶”的排序,他的排序思路是这样的:先以个位数的大小来对数据进行排序,接着以十位数...

    帅地

扫码关注云+社区

领取腾讯云代金券