文档章节

【算法】6 比较排序之外学习新的线性时间排序

NoMasp
 NoMasp
发布于 2015/09/08 21:49
字数 2812
阅读 2
收藏 0

回顾比较排序

相信阅读过前面5篇博文的童鞋们已经发现了“在排序的最终结果中,各元素的次序依赖于它们之间的比较”。于是乎,这类排序算法被统称为”比较排序“。

比较排序是通过一个单一且抽象的比较运算(比如“小于等于”)读取列表元素,而这个比较运算则决定了每两个元素中哪一个应该先出现在最终的排序列表中。

声明:下面通过在维基百科中找到的非常完美的图示来介绍一系列比较排序。

插入排序

在该系列的【算法】1中我们便介绍了这个基本的算法,它的比较过程如下:

这里写图片描述

以下是用插入排序对30个元素的数组进行排序的动画:

这里写图片描述

选择排序

选择排序的比较过程如下:

这里写图片描述

其动画效果如下:

这里写图片描述

归并排序

前面多次写到归并排序,它的比较过程如下:

这里写图片描述

归并排序的动画如下:

这里写图片描述

堆排序

在该系列的【算法】4中我们便介绍了快排,构建堆的过程如下:

这里写图片描述

堆排序的动画如下:

这里写图片描述

快速排序

在该系列的【算法】5中我们便介绍了快排,它的比较过程如下:

这里写图片描述

快速排序的动画如下:

这里写图片描述

另外一些比较排序

以下这些排序同样也是比较排序,但该系列中之前并未提到。

Intro sort

该算法是一种混合排序算法,开始于快速排序,当递归深度超过基于正在排序的元素数目的水平时便切换到堆排序。它包含了这两种算法优良的部分,它实际的性能相当于在典型数据集上的快速排序和在最坏情况下的堆排序。由于它使用了两种比较排序,因而它也是一种比较排序。

冒泡排序

大家应该多少都听过冒泡排序(也被称为下沉排序),它是一个非常基本的排序算法。反复地比较相邻的两个元素并适当的互换它们,如果列表中已经没有元素需要互换则表示该列表已经排好序了。(看到列表就想到半年前在学的Scheme,欢迎大家也去看看,我开了2个专栏来介绍它们)

上面的描述中已经体现了比较的过程,因而冒泡排序也是一个比较排序,较小的元素被称为“泡(Bubble)”,它将“浮”到列表的顶端。

尽管这个算法非常简单,但大家应该也听说了,它真的非常的慢。

冒泡排序的过程如下:

这里写图片描述

冒泡排序的动画演示:

这里写图片描述

其最好情况、最坏情况的运行时间分别是: Θ(n) Θ(n2)

奇偶排序

奇偶排序和冒泡排序有很多类似的特点,它通过比较在列表中所有的单双号索引的相邻元素,如果有一对是错误排序(也就是前者比后者大),那么将它们交换,之后不断的重复这一步骤,直到整个列表排好序。

而鉴于此,它的最好情况、最坏情况的运行时间均和冒泡排序相同: Θ(n) Θ(n2)

奇偶排序的演示如下:

这里写图片描述

下面是C++中奇偶排序的示例:

template <class T>
void OddEvenSort (T a[], int n)
{
    for (int i = 0 ; i < n ; i++)
    {
         if (i & 1) // 'i' is odd
         {
             for (int j = 2 ; j < n ; j += 2)
             {     
                  if (a[j] < a[j-1])
                      swap (a[j-1], a[j]) ;
             }
          }
          else
          {  
              for (int j = 1 ; j < n ; j += 2)
              {
                   if (a[j] < a[j-1])
                       swap (a[j-1], a[j]) ;
              } 
          }
    }
}

双向冒泡排序

双向冒泡排序也被称为鸡尾酒排序、鸡尾酒调酒器排序、摇床排序、涟漪排序、洗牌排序、班车排序等。(再多再华丽丽的名字也难以弥补它的低效)

和冒泡排序的区别在于它是在两个方向上遍历列表进行排序,虽然如此但并不能提高渐近性能,和插入排序比起来也没太多优势。

它的最好情况、最坏情况的运行时间均和冒泡排序相同: Θ(n) Θ(n2)

这里写图片描述


排序算法的下界

我们可以将排序操作进行得多块?

这取决于计算模型,模型简单来说就是那些你被允许的操作。

决策树

决策树(decision tree)是一棵完全二叉树,它可以表示在给定输入规模情况下,其一特定排序算法对所有元素的比较操作。其中的控制、数据移动等其他操作都被忽略了。

这里写图片描述

这是一棵作用于3个元素时的插入排序的决策树。标记为 i:j 的内部结点表示 ai aj 之间的比较。

由于它作用于3个元素,因此共有 A33=6 种可能的排列。也正因此,它并不具有一般性。

而对序列 <a1=7,a2=2,a3=5> 和序列 <a1=5,a2=9,a3=6> 进行排序时所做的决策已经由灰色和黑色粗箭头指出了。

这里写图片描述

决策树排序的下界

如果决策树是针对n个元素排序,那么它的高度至少是 nlgn

在最坏情况下,任何比较排序算法都需要做 Ω(nlgn) 次比较。

因为输入数据的 Ann 种可能的排列都是叶结点,所以 Annl ,由于在一棵高位 h 的二叉树中,叶结点的数目不多于 2h ,所以有:

n!l2h

对两边取对数:

=> lg2hlgn!

=> lg2h=hlg2lgn!

又因为:

lg2<1

所以:

nlgn!=Ω(nlgn)

因为堆排序和归并排序的运行时间上界均为 O(nlgn) ,因此它们都是渐近最优的比较排序算法。

线性时间排序

计数排序

计数排序(counting sort)的思路很简单,就是确定比x小的数有多少个。加入有10个,那么x就排在第11位。

严谨来讲,在计算机科学中,计数排序是一个根据比较键值大小的排序算法,它也是一个整数排序算法。它通过比较对象的数值来操作,并通过这些计数来确定它们在即将输出的序列中的位置。它的运行时间是线性的且取决于最大值和最小值之间的差异,当值的变化明显大于数目时就不太适用了。而它也可以作为基排序的子程序。

COUNTING-SORT(A,B,k)
1   let C[0...k] be a new array
2   for i=0 to k
3       C[i]=o
4   for j=1 to A.length
5       C[A[j]]=C[A[j]]+1
6   // C[i] now contains the number of element equal to i.
7   for i=1 to k
8       C[i]=C[i]+C[i-1]
9   // C[i] now contains the number of element less than or equal to i.
10  for j=A.length downto 1
11      B[C[A[j]]]=A[j]
12      C[A[j]]=C[A[j]]-1

第2-3步,C数组的元素被全部初始化为0,此时耗费 Θ(k) 时间。

第4-5步,也许不太好想象,其实就是在C数组中来计数A数组中的数。比如说, A 数组中元素”3”有4个,那么 C[3]=4 。此时耗费 Θ(n) 时间。

第7-8步,也是不太好想象的计算,也就是说如果 C[0]=1 C[1]=4 ,那么计算后的 C[0] 不变, C[1]=5 。此时耗费 Θ(k) 时间。

第10-12步,把每个元素 A[j] 放到它在输出数组 B 中的合适位置。比如此时的第一次循环,先找到 A[8] ,然后找到 C[A[8]] 的值,此时 C[A[8]] 的意义就在于 A[8] 应在B数组中的位置。完成这一步后将 C[A[8]] 的值减一,因为它只是一个计数器。这里耗费的时间为 Θ(n)

这里写图片描述

k=O(n) 时,计数排序的运行时间为 Θ(n)

基数排序

基数排序(radix sort)是一个古老的算法,它用于卡片排序机上。说来也巧,写这篇博客的前一天晚上还在书上看到这种机器,它有80列,每一列都有12个孔可以打。

它可以使用前面介绍的计数排序作为子程序,然而它并不是原址排序;相比之下,很多运行时间为 Θ(nlgn) 的比较排序却是原址排序。因此当数据过大而内存不太够时,使用它并不是一个明智的选择。

这里写图片描述

关键在于依次对从右往左每一列数进行排序,其他的列也相应移动。

桶排序

这倒是一个有趣的算法了,它充分利用了链表的思想。

桶排序(bucket sort)在平均情况下的运行时间为 O(n)

计数排序假设 n 个输入元素中的每一个都在0和k之间,桶排序假设输入数据是均匀分布的,所以他们的速度都非常快。但并不能因为这些是假设就说它们不实用不准确,真正的意义在于你可以根据情况选择合适的算法。比如说,输入的n个元素并不是均匀分布的,但它们都在0到k之间,那么就可以用计数排序。

说到桶,我想到的是装满葡萄酒的酒桶以及装满火药的火药桶。这里是桶是指的算法将 [0,1) 区域划分为了 n 个相同大小的空间,它们被称为桶。

既然有了这个划分,那么就要用到它们。假设输入的是n个元素的数组A,且对于所有的i都有 0A[i]<1 。你也许会觉得怎么可能输入的数组元素都凑巧满足呢,当然不会这么凑巧,但是你可以人为地改造它们呀。比如 <10,37,31,87> ,你可以将它们都除以100,得到 <0.10,0.37,0.31,0.87>

还需要一个临时的数组B[0…n-1]来保存这些桶(也就是链表),而链表支持搜索,删除和插入。关于链表的部分后面的博客中会有详细介绍。

BUCKET-SORT(A)
1   n=A.length
2   let B[0...n-1] be a new array
3   for i=0 to n-1
4       make B[i] an empty list
5   for i=1 to n
6       insert A[i] into list B[小于等于nA[i]的最大整数]
7   for i=0 to n-1
8       sort list B[i] with insertion sort
9   concatenate the lists B[0],B[1],...B[n-1] together in order

这里写图片描述

学习算法一定要体会到这种算法内每一步的改变,也要体会不同算法之间的演化和进步。在后面的链表中,我会更加侧重于思路以及算法的进化。



感谢您的访问,希望对您有所帮助。 欢迎大家关注、收藏以及评论。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/46380027

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
十大经典排序算法(动图演示)转

0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 ...

o0无忧亦无怖
2018/07/05
132
0
菜鸟学习历程【15-1】直接插入排序

排序就是按照递增或者递减的次序整理文件中的记录。 排序分为稳定排序和不稳定排序,什么是稳定,什么又是不稳定? 例如:3 15 8 8 6 9 在上述6个数字中的排序过程中,如果将两个8的位置交换...

leessang_bo
2017/12/02
0
0
js实现十大经典排序算法(动图演示)

0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。 非比较类...

duduYZ
08/31
42
0
冒泡排序算法(起泡排序)及其C语言实现

冒泡排序 起泡排序,别名“冒泡排序”,该算法的核心思想是将无序表中的所有记录,通过两两比较关键字,得出升序序列或者降序序列。 例如,对无序表{49,38,65,97,76,13,27,49}进行升序...

这个人很懒什么都没留下
03/08
0
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

32位与64位Linux系统下各类型长度对比

64 位的优点:64 位的应用程序可以直接访问 4EB 的内存和文件大小最大达到4 EB(2 的 63 次幂);可以访问大型数据库。本文介绍的是64位下C语言开发程序注意事项。 1. 32 位和 64 位C数据类型...

mskk
26分钟前
6
0
Vue 实现点击空白处隐藏某节点(三种方式:指令、普通、遮罩)

在项目中往往会有这样的需求: 弹出框(或Popover)在 show 后,点击空白处可以将其 hide。 针对此需求,整理了三种实现方式,大家按实际情况选择。 当然,我们做项目肯定会用到 UI 框架,常...

张兴华ZHero
32分钟前
7
0
SpringBoot激活profiles你知道几种方式?

多环境是最常见的配置隔离方式之一,可以根据不同的运行环境提供不同的配置信息来应对不同的业务场景,在SpringBoot内支持了多种配置隔离的方式,可以激活单个或者多个配置文件。 激活Profi...

恒宇少年
34分钟前
8
0
PDF修改文字的方法有哪些?怎么修改PDF文件中的文字

PDF修改文字一直以来都是一个难以解决的问题,很多的办公族在办公的时候会有修改PDF文件中的文字的需要,可是PDF文件一般是不能进行编辑和修改的,难道就没有什么办法解决这个问题了嘛?不要...

趣味办公社
37分钟前
5
0
企业组织中采用服务网格的挑战

作者:Christian Posta 译者:罗广明 原文:https://blog.christianposta.com/challenges-of-adopting-service-mesh-in-enterprise-organizations/ 编者按 本文作者介绍了企业组织采用服务网...

jimmysong
47分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部