技术时间到!#1——简单的排序算法

EaseCation能够承载海量玩家,与它实现的算法紧密相关。更快的算法,能让服务器变得更加强劲,处理更多玩家的交互信息。

今天开始,我们尝试梳理简单的算法。我们希望让更多玩家理解,游戏开发背后要做出哪些努力。这次的文章,将从最简单的算法——排序算法开始。

让没有顺序的值变得有序,就称作排序。“有序”的定义,更科学地讲是满足“全序关系”可达到的状态。我们撇开计算机科学的严格定义,先试着给出最简单的、为数字排序的方法。

冒泡排序

有一天,史蒂夫和安娜在池塘边玩耍。他们马上对石头产生了兴趣:怎样把石头,从小到大地排成一行呢?

“我们来交换这些石头吧。只要每个石头,都比左边的石头大:石头就能排成顺序了。”史蒂夫说,“只要交换的时候,不要把小的石头放在右边,就可以了。”

池塘里的小鱼吐着泡泡,安娜想到了最直接的方法。“我们从前到后,比较每一对石头,只要比右边的石头更大,我们就把它换右边去。”

“……就像小鱼吐泡泡一样,泡泡越往上浮,越大。这样,所有大的石头都在一侧后,石头就有顺序了。”史蒂夫高兴地接着话:“我们不要太累,小的石头不要在右边,这样就行了。”

一排石头(图源网络)

在这里,我们把一行石头,看成计算机处理的数字。数字的顺序应当最终正确;顺序不正确的一对数字,我们称之为逆序对。只要交换数字,让顺序不正确的数字不再出现,排序就完成了。

如果能够看到这里,你已经明白了冒泡排序的思想。恭喜你!

来,我们开始编写下面的Rust代码:

冒泡排序的朴素实现

这里,T是数据的类型。我们提供约束Ord,说明T的比较满足全序关系。T的全序关系,意味着对于所有T的可能取值,我们都能给两个T值分出大小关系。

我们给定的变量arr,是一个切片类型的可变借用,包含数据本身和它的长度。

迭代变量i和j,用来遍历所有的数据对;如果它是逆序对,我们就使用切片类型的swap函数,交换这两个数据值。

所有的步骤完成后,切片中所有的数字将是有序的——我们的排序过程就这样完成了。在数据已经有序的情况下,冒泡排序是相当快速的。

让我们回顾一下:在生活中,还有哪些时候,我们会给数字排序呢?想一想,你是怎么做的?

选择排序

有些学习勤快的同学已经给出答案了:我会整理桌上的书本。我挑出最长的书本,放在最下面;再拿出第二长的,也放在那里。最终,我将会有一摞从大到小排序的书本。

这就是我们对选择排序给出的理解。处理还没有顺序的数据,只需要挑出最大,或最小的一个,然后再处理剩下的数据,做到最后就可以了。

我们来给出它的Rust代码:

选择排序算法

我们仍然约束T为给定全序关系的类型,给定切片参数arr。

为了实现选择排序,我们从前向后迭代。在前i个变量有序的前提下,我们在剩下的变量中,取最小的一个,和无序变量的第一个交换。最终,我们就得到了有序的切片。

一般来讲,选择排序的速度比冒泡排序慢。虽然速度慢了点,但是它需要交换操作的次数比较少。在交换操作非常耗时的前提下,使用选择排序,会比冒泡排序节省更多时间。

你可能喜欢玩扑克牌。这时候,你也许已经领悟了另一个算法——

插入排序

当我们拿到洗乱的扑克牌,我们会不断抽出扑克牌。当抽出一张牌,我们会将它插入另一个位置。我们要让插入之后,它的一侧,都是比它小的牌;另一侧,都是比它大的牌。重复这个过程,洗乱的扑克牌就有顺序了。

这种像整理扑克牌一样,不断插入来排序的方法,我们给它一个名字:插入排序

来来来,写代码的时间到啦~这是它的Rust代码哦~

插入排序(Rust实现)

插入排序的过程相当容易。在变量数较少的前提下,它和选择排序需要更少的比较次数。如果数字已经基本有序,插入排序也能拥有不错的性能。

上面讲到的三种排序算法,是排序算法中比较简单的;但在数据规模n上升的前提下,它们都需要把数据切片遍历两次,它们需要的时间为n²

我们粗略地给出时间复杂度的定义:解决一定规模的问题,需要的大致时间可以用n表示,我们用记号大O,表示它的时间复杂度。对冒泡排序、选择排序和插入排序而言,需要的时间为n²,所以它们的时间复杂度都是O(n²)。

当然,我们更希望冲击更低的时间复杂度——这意味着我们的排序算法,将花费最少的时间。堆排序是一种简单的方法,为了优化时间开销,我们需要学习新的数据结构:堆。

堆排序

是一种数据结构,它可以描述一类数组或切片。

举一个有序切片的例子。假定arr有序,我们给出arr的表示:

切片arr的内存表示。来源:https://blog.csdn.net/lyq_12/article/details/84133836

这里,arr已经从大到小排序。

我们可以把堆表示成完全二叉树。根结点的下标为0,我们把0和它对应的数据放到树根的位置。每个结点的下标乘以2后加上1,可以得到它左孩子的下标;左孩子再下标加上1,是右孩子的下标。

给出大顶堆的定义。大顶堆必须满足:双亲结点的数据,大于所有两个孩子的数据。所以,根结点的数据,一定是大顶堆中所有数据里最大的一个。

切片arr是有序的,它可以表示成大顶堆。表示如下图:

大顶堆的逻辑表示

一般的切片是没有顺序的,它们不满足堆的定义。我们需要调整数据的位置,使之满足堆的定义;这个操作称为建堆

比如对数据[4, 6, 5, 8, 9],下图我们建堆的第一步,我们从最后一位开始。我们发现数字9和它的双亲结点6,不满足双亲结点大于孩子结点,这时候需要把它们交换。

建堆示例(1)

交换后我们发现,数字9和它的父亲结点4,不满足双亲结点大于孩子结点。我们再次交换。

建堆示例(2)

但是交换之后,4和它之下的结点又不满足堆的定义。我们对索引1、3、4,将它们看成一个没有整理的子树,把1看成根结点,再次执行上面的过程,我们将得到一个子堆。最终,我们得到了一个整理好的堆,建堆过程就完成了。

建堆完成后,最大的元素就在位置0处。我们需要从小到大排序,将它和最后一个元素交换;这样最大的元素,就在对应的位置上了。但是,这个步骤将破坏堆的性质,交换来的数字成为新的根结点,但它将小于它的左右儿子包含的数据。我们将调整剩下的数组,维持堆的性质。交换和维持的过程,加起来称为出堆

延续上面的例子。我们将9和4交换,9将成为有序的元素之一。

出堆示例(1)

这个过程破坏了堆的性质,我们重新从4开始整理这个完全二叉树,使之重新成为堆。

出堆示例(2)

重复这个过程,最终我们将得到有序的切片:[4, 5, 6, 8, 9]。排序完成了。

有序的切片

在这个过程中,我们建立一个堆并保持它的性质。如果有n个元素,我们总共需要出堆n次。每次出堆,我们在完全二叉树的每一层,需要调整一次次序,来维护堆的性质。

来,用Rust写出它的代码:

Rust代码(堆排序)

代码的思路和图示相同。我们在adjust_heap函数里递归,来维持堆中子堆的性质;递归的层数并不会很深。在出堆操作时,我们可变借用切片的子切片,来表示剩下需要再次回到堆性质的元素。这些过程后,我们的代码将迅速得到排序的结果。

我们来做简单的计算,来看它是否满足优化时间复杂度的需求。由完全二叉树的性质得到,它的最大层数h是向上取整的log₂(n)。所以在n次出堆中,我们各需要操作log₂(n)次。建堆的时间将小于出堆的时间,所以排序的时间复杂度为O(nlogn);它小于前三个排序算法的O(n²)。

这是我们得到的第一个,时间复杂度小于O(n²)的排序算法。这个算法维护一个称为堆的数据结构,因此我们叫它堆排序

使用堆排序替代之前的几种排序方法,我们的算法已做出优化,能节省大量运算时间。非常好!

心得&体会

排序算法是所有算法中最简单的一种。它依然能有更复杂的优化和思路;但作为算法的基础,我们学习后,最容易理解算法的价值。算法没有最好,只有最符合。最复杂的排序算法不过百行;但另有些改变架构的复杂情况,优化的代码将达到数十万行——所以为了优化算法花费的时间,我们仍然需要学习大量的知识,阅读大量学术论文,体会到游戏开发是需要不停研究的领域。

本文作者:洛佳(EaseCation团队 开发组)

喜欢的话请三连吧~

本文禁止转载或摘编

-- --
  • 投诉或建议
评论