标签归档:排序

优先队列与堆排序

队列(Queues)是应用中常见的数据结构,一个队列至少有“入队”和“出队”两个基本操作。队列具有“先入先出(First In First Out, FIFO)”性质,就像排队一样,入队会将新元素插入到队列的末尾,而出队会取出队列中排在最前的(也是最早入队的)一个元素。

优先队列(Priority Queues)的接口与基本队列一样,至少有“入队”和“出队”两个基本操作。与基本队列不同的是,优先队列的出队顺序不是先入先出,而是以队列中元素的健作为优先级出队,键最大(或最小)的元素最先出队,其次是键次大(或次小)的元素。键大优先出队的优先队列称为面向大元素的优先队列;键小优先出队的优先队列称为面向小元素的优先队列。为了方便,在没有特别说明的情况下,下文所有提到的优先队列均指面向大元素的优先队列。

要实现一个高效的优先队列并不十分容易,一个直观而简易的实现方式是使用有序链表。设 L 是一个按从大到小顺序排列的链表,使用这个链表充当优先队列。当有一个元素 N 需要入队时,只需从头到尾遍历队列,找到插入 N 之后不会破坏链表有序性的位置,将 N 插入链表;当需要出队一个元素时,因为链表的有序性保证了第一个元素一定是最大的元素,因此只需直接取出链表中第一个元素返回,并删除这个元素。

使用链表构建的优先队列入队效率比较低,假设队列长度是 n 那么入队平均需要遍历 n / 2 个结点;而它的出队效率又非常高,显然,它出队的时间复杂度是常数 1。造成链表优先队列入队效率底的根本原因是搜索的效率低,在一个有序的数据结构中逐个元素顺序搜索是不明智的。以往的经验告诉我们,在有序的数据集合中进行查找,高效的做法是用二分的思想。而链表不支持随机访问,在数组中运用的二分法查找在链表中是无效的。

实现优先队列,另一个更聪明的办法是用二叉树来组织数据。维护一棵始终满足以下条件的二叉树,就能实现一个较高效的优先队列:

  1. 是一棵完全二叉树;
  2. 每个结点的键都比它的非空子结点的键大。

通常的二叉树是以链式结构组织的,树各个结点的物理存储位置是离散的,每个结点通过保存该结点的两个子结点以及父结点的引用(或“指针”)来彼此关联。而为了实现优先队列,我们按从上到下、从左到右的顺序将一棵二叉树组织到数组里,所有结点都在数组中连续存放,形成一个二叉堆。按习惯,二叉堆又简称“”,下文也遵循习惯使用简称“堆”指二叉堆。之所以用堆的形式来组织优先队列而不是通常的链式结构,是因为堆能更快更容易地实现优先队列入队和出队的操作,具体的理由总结如下:

  1. 完全二叉树除了底部外所有结点的子结点全都非空,且生长点只能在树的底部,用数组来存放它既没有空位,又无需在插入之后移动元素;
  2. 数组支持随机访问,访问效率优于链式结构的二叉树;
  3. 无需每个结点都保存其子结点或父结点的引用,只需对自身的索引进行简单的运算即可找到子结点或父结点;
  4. 插入新元素时,能非常容易地找到插入点。

假设用数组 a[] 来组织上面说到的堆,为了方便,元素 a[0] 置空不用,从 a[1] 开始存放堆的所有元素。这样,堆的根结点即是 a[1],假设存在某个结点 a[n] (n > 1),那么它的父结点就是 a[n / 2],它的左子结点是 a[2 * n],它的右子结点是 a[2 * n + 1]。

实现对优先队列的入队就是当向堆插入一个元素,先将新的元素插入到堆的尾部成为一个新结点。此时,这个结点很可能并不比它的父结点小,因此堆的性质之一“每个结点的键都比它的非空子结点的键大”可能会遭到破坏,必须做一些处理使堆重新满足这个条件。

这些处理称为结点的“上浮”。结点上浮的目的是将新插入的结点移动到合适的位置,使这个结点既大于它所有的子结点,又小于它的父结点。结点上浮的操作算法很简单:比较被上浮的结点与它的父结点的大小,如果当前结点大于父结点,则交换它们的位置;然后重复上述操作,直到当前结点不大于父结点或者当前结点已经是根结点。下面的 Java 代码实现了堆结点上浮的操作。

实现对优先队列的出队就是读出堆顶部的结点,然后删除它。删除一般二叉树的一个结点,就有可能留下两个孤立的子树,此时需要在树中删出一个没有非空子结点或只有一个非空子结点的结点来填补到删除结点后产生的空缺中。删除堆顶的一个结点,同样需要找一个结点来填补空缺,最容易的办法是删出堆底的结点,填补到堆顶空缺的位置,然后堆大小减 1。这时填补到堆顶的结点几乎一定是会比它的左右子结点都小的,不满足优先队列堆要求的条件,需要做一些处理使堆重新满足条件。

这些处理称为结点的“下沉”。结点下沉的目的是将处于堆顶部的小结点向堆底移动,使这个结点既大于它所有的非空子结点,又小于它的父结点。像结点的上浮操作一样,结点的下沉操作也很容易实现。先从结点的左右子结点中找出非空且较大的那一个,被下沉的结点与之交换,重复这个过程,直到当前结点大于它的所有非空子结点或者它的所有子结点均为空。下面的 Java 代码实现了堆结点的下沉操作。

如果将一串乱序数据全部入队到一个优先队列中,然后从优先队列中出队所有的数据,数据出队时将是有序的,这无疑提供了一个新的排序思路。

堆排序就是利用了上述优先队列思想的排序算法。对一个乱序的数组进行堆排序时,分为两个阶段,第一阶段称为建堆,将数组原地组织成一个符合上文中描述的条件的堆;另一个阶段把这个堆当作优先队列,不断地出队元素,并把出队的元素填到因出队而空缺的位置。当堆逐步缩小直至为空时,堆排序完成,数组变成了有序数组。

如何对一个数组实现原地建堆是一个值得思考的问题,为了讨论问题方便,先定义“堆有序”指一个堆满足上文提到的优先队列堆的所有条件。显然,一个大小为 1 的堆一定是堆有序的。如果一个堆 H 的左右两个子堆都是堆有序的,只要对这个堆的根结点做一次下沉操作,堆 H 也一定会转化为一个堆有序的堆。设有一个乱序数组 a[1…n],把它看作一个堆,Hi 表示以 a[i] 为堆顶的子堆,则可以得出 Hn/2+1, Hn/2+2, …, Hn 均是大小为 1 的子堆,换言之,这些子堆都是堆有序的,数组 a 中有半数子堆是堆有序的。为了使整个数组都成为堆有序的堆,只要先后对 a[n/2], a[n/2-1], …, a[1] 执行下沉操作即可。

建堆完成后,就可以开始第二步骤了。将数组当作一个优先队列,出队一个元素 N1,此时 a[n] 处因出队产生了一个空缺,将 N1 填补到 a[n] 处,继续出队 N2,填补到 a[n-1] 处,直到出队 Nn,填补到a[1] 处,数组 a 排序完成。

值得注意的是,在实际运用中,大部分程序设计语言的数组第一个元素的索引并不是 1 而是 0,但只要在上述算法的基础上对索引稍作处理即可实现堆排序。

堆排序无需额外的空间,时间复杂度也能达到比较理想的 O(nlogn) 的级别,是一种优秀的排序算法。

本文提到的全部算法均已用 Java 实现,代码托管于 GitHub,查看

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=250 )

排序

将一个数据集合按照给定的规则以一定的顺序重新排列,这个操作称为排序。排序算法在计算机程序设计中的重要性和应用的广泛性毋须多言,几乎所有高级计算机语言都带有排序算法的库,在程序开发过程中不必再造一次轮子,但掌握排序算法的原理仍然是非常必要的。本文将从一个最直观的排序算法——选择排序开始,不断探讨排序算法的改进和优化空间,期间会谈到多个经典的排序算法。排序算法是如此简洁而优雅:不论是简单直观的选择排序算法,还是应用最广泛而高效的快速排序算法,实现它们的核心代码最长也不过寥寥二十几行。因此,本文提到的每个算法,除了必要的图文描述外,还会配上实现它们的 Java 代码。对于排序算法来说,代码是最好的描述。

选择排序

选择排序是本文所有算法中最直观的,也是效率最低的排序算法。了解选择排序的算法可以帮助理解排序的基本逻辑:比较元素的大小并视情况交换它们。选择排序算法可以很简单地描述如下:从数组的第 0 个元素开始,找出数组中最小(大)的那个元素,并和第 0 个元素交换位置;然后再从第 1 个元素开始,重复以上的过程,直到数组所有的元素都完成一轮这样的操作。这个操作非常容易理解,也能用很简短的程序实现。下面是实现选择排序的 Java 代码,其中 swap(a, x, y) 方法的作用是交换数组 a 中索引为 x 和 y 的两个元素,后面的代码将多次用到这个方法,不再说明。

可以看到,选择排序的性能很稳定,如果数组的长度是 n,不管初始数组内的元素如何排列,排序操作完成时一定会发生 n-1 + n-2 + … + 1 = n(n-1)/2 次比较。

插入排序

选择排序的问题之一是每一轮搜索都执着地要找出最小的那个元素,然而要找出最小的元素,必须将当前集合里所有的元素都访问一遍。就算被排序的数组本身已经是有序的了,选择排序的执行时间跟数组是乱序情况下也是一样的。

插入排序在这一点上做了一些改进。和选择排序一样,插入排序在执行过程中保持当前索引左边的元素集合是有序的;但与选择排序不同的是,这些元素并不一定是整个数组中最小的那部分。假设一个对数组 a 的选择排序在进行过程中,当前的有序集合是 a[0…m],右边未排序的集合是 a[m+1…n],那么只要将元素 a[m+1] 与它左边的元素进行比较并视情况交换位置,直到使 a[0…m+1] 也成为一个有序的数组。将上述操作继续进行,直到整个数组都是有序的。插入排序的 Java 实现代码如下:

插入排序的性能是不稳定的,当被排序的数组已经是一个有序数组时,假设数组的长度是 n,执行一次插入排序只要比较 n 次;而当被排序数组正好是期望顺序的倒序时,插入排序的性能最是坏的情况,需要比较的次数与选择排序完全一样。当被排序的数组存在较大比例的有序部分时,插入排序的性能是很好的,然而,它的缺点是性能不够稳定。

希尔排序(Shell Sort)

希尔排序得名于它的设计者 Donald Shell。希尔排序是在插入排序的基础上改进后的排序算法。在插入排序中,一个相对较大的元素每次比较只能向前移动一个位置,经常需要移动多次才能到达它应到的地方,这限制了插入排序的性能。

希尔排序的思想是将一个数组中彼此间隔为 h 的元素分组,一共有 h 个分组,对每个分组分别执行插入排序,完成后这个数组称为“h 有序数组”。希尔排序的方法是先取一个较大的 h(不大于 n / 2),使数组成为 h 有序数组,然后再适当减小 h 的值,重复上面的操作,直到最后 h = 1,相当于一次普通的插入排序。希尔排序的 Java 实现代码如下。

希尔排序首先使用较大的 h 值进行粗略的排序,较大幅度地移动元素。每完成一轮都增加了数组的有序性,使下一轮 h 更小的更精细的排序能较快地进行,最后当 h = 1 时,数组已经是基本有序的状态了,只要对个别元素进行距离较短的调整即可完成排序。实践表明,在对一般乱序的数组进行排序时,希尔排序的性能远优于插入排序。

对于 h 序列的选择有非常多的研究,对不同的 h 序列进行排序时性能的差别较大,但并没有人证明某个序列的性能是最优的。上述代码中的 step 和 nextStep 方法是返回第一个 h 的值以及后续 h 的值,本文并没有给出,我在实现时参考了《Algorithms (4th Edition)》一书中的序列,有兴趣请移步我的 GitHub 查看这个算法的完整实现。

归并排序(Merge Sort)

在高效算法中,我们会经常见到一种分而治之的思想,即把一个复杂的问题拆分成两个较简单的问题分别处理,简单的问题得解后复杂的问题也就已经解决了。归并排序是将分治和递归结合的一种排序思路:

  1. 拆分:如果数组的长度等于 1,数组已经是有序状态,直接返回;否则将数组拆分成左右两个部分;
  2. 递归:左右两个部分分别再进行归并排序,得到两个有序的部分;
  3. 合并:两个有序的部分合并,数组排序完成。

和其他递归思想的算法一样,把问题不断地拆解最终会得到一个不需要解决的问题:排序长度为 1 的数组,这时候直接返回即可。将两个有序的数组合并也非常容易实现,下面是归并排序的 Java 实现,其中 11-19 行的 while 循环完成了合并操作。

归并排序的效率比之前提到的所有算法都高,达到了 O(nlogn) 的级别,而且它的效率还难得地稳定。事实上,归并排序已经是具有实用价值的排序算法了。归并排序的一个缺点是需要一个额外的辅助数组来暂存合并的结果,这个数组的最大长度与被排序的数组长度相同。

快速排序(Quick Sort)

如果说归并排序是牺牲了一定的空间来换取时间上的最优解,那么快速排序则同时满足了时间和空间上的最优;它不像归并排序一样需要一个额外的辅助数组,更可贵的是,描述和实现它仍然非常简单。

与归并排序一样,快速排序也是一种分治的算法:

  1. 切分:如果被排序的数组长度是 1,无需排序;否则选择一个切分元素 s,移动 s 和其他的元素,保证 s 左边的元素都不大于 s,并且 s 右边的元素都大于 s;
  2. 递归:以 s 为分界,分别对 s 左边的子数组和 s 右边的子数组做快速排序操作。

上述操作完成后数组排序完成。在实现中,通常取第 0 个元素作为切分元素。对于长度为 l(l > 1) 的数组 a,切分操作简单描述如下:

初始令索引 i = 1, 索引 j = l – 1。i 向右搜索,直到找到 i 满足 a[i] > a[0];j 向左搜索,直到找到 j 满足 j[i] < a[0],此时交换元素 a[i] 和元素 j[i]。i 和 j 继续分别向右和向左搜索,直到 i == j,即两个索引相遇。此时比较 a[0] 与相遇处 a[i] 的值,当 a[0] >= a[i] 时交换 a[0] 与 a[i],索引 i 处于切分点;否则交换 a[0] 与 a[i – 1],索引 i – 1 处于切分点,至此切分操作完成。下面是快速排序算法的 Java 实现,其中 7-16 行的 while 循环实现了切分操作。

快速排序一个潜在的缺点在于它是一种不稳定的排序算法,考虑对一个已经有序的数组进行快速排序,会发现每次切分点都在数组的边缘,这时算法的效率将退化到 O(n2) 级别。为了规避这个缺陷,在实际应用中,在进行快速排序之前需要对被排序数组进行随机乱序处理。

性能测试

为了测试上述所有排序算法的性能及算法实现的正确性,我设计了一个测试用例,以几种不同长度、不同排列顺序的数组分别测试排序,并统计运行耗时。测试用例所用的数组有:

  1. 长度 10,000 取值范围 0-100,000 的随机乱序数组;
  2. 长度 100,000 取值范围 0-1,000,000 的随机乱序数组;
  3. 长度 1,000,000 取值范围 0-10,000,000 的随机乱序数组;

测试结果如下(数据单位是 ms):

 

10,000

100,000

1,000,000

SS

122

14,851

*

IS

149

16,657

*

ShS

10

66

1,485

MS

7

84

528

QS

9

92

472

* 超过 60,000 ms 被中止测试

测试结果显示,归并排序和快速排序性能优异,而希尔排序在数组长度较小的情形下有较好的性能。 选择排序和插入排序在测试中表现相对较差,甚至在大数组测试中迟迟没有出现结果,只好中止测试。

本文提到的所有算法和测试用例的源代码均托管于 GitHub,查看

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=228 )