所谓排序,是指将数据按照键重新排列为升序(从小到大)或降序(从大到小)的处理。举个例子,将整数数列A={4, 1, 3, 8, 6, 5} 按升序排列是A={1, 3, 4, 5, 6, 8},按降序排列则是A={8, 6, 5, 4, 3, 1}。

我们用数组来管理这些数列形式的输入数据,然后通过循环处理完成元素的交换和移动,最终实现数据排序。

一般说来,我们的数据都是一张具有多个属性的表,所以在排序时需要以某种特定属性为基准,这个特定属性就称为“排序键”(Sort Key)。比方说,我们现在要处理一份由“ID”“问题A 的得分”“问题B 的得分”组成的排名数据。假设数据如表3.1 所示按ID 顺序输入,那么按“A 的得分”降序排列后的结果就如表3.2 所示。

enter image description here

管理作为排序对象的数据时,需要用到结构体或类的数组。

我们在设计或选择算法时,复杂度是重要的衡量标准之一。不过,对于排序算法而言,还必须将“稳定排序”(Stable Sort)纳入考量。所谓稳定排序,是指当数据中存在2 个或2 个以上键值相等的元素时,这些元素在排序处理前后顺序不变。

比如,我们将上面按ID 顺序输入的数据以“B 的得分”为基准进行降序排列(表3.3),可能会得到如表3.4 所示的输出。

enter image description here

这份输入数据中,player2 和player4 的问题B 的得分相同,并且输入时player2 在前player4 在后。稳定的排序算法能保证按照player2 → player4 的顺序输出,但不稳定的排序算法就有可能出现按player4 → player2 顺序输出的情况。

时至今日,人们已研究、开发出了许多种排序算法,它们的机制各不相同。因此我们要留意以下特征,力求选出最合适的算法。

复杂度与稳定性

除保存数据的数组以外是否还需要额外内存

输入数据的特征是否会对复杂度造成影响

评论

本文目前还没有评论……

我要评论

需要登录后才能发言
登录未成功,请修改提交。