5.6.排序

排序是以某种顺序从集合中放置元素的过程。例如,单词列表可以按字母顺序或按长度排序。城市列表可按人口,按地区或邮政编码排序。我们已经看到了许多能够从排序列表中获益的算法(回忆之前的回文例子和二分查找)。

有许多开发和分析的排序算法。表明排序是计算机科学的一个重要研究领域。对大量项进行排序可能需要大量的计算资源。与搜索一样,排序算法的效率与正在处理的项的数量有关。对于小集合,复杂的排序方法可能更麻烦,开销太高。另一方面,对于更大的集合,我们希望利用尽可能多的改进。在本节中,我们将讨论几种排序技术,并对它们的运行时间进行比较。

在分析特定算法之前,我们应该考虑可用于分析排序过程的操作。首先,必须比较两个值以查看哪个更小(或更大)。为了对集合进行排序,需要一些系统的方法来比较值,以查看是否有问题。比较的总数将是测量排序过程的最常见方法。第二,当值相对于彼此不在正确的位置时,可能需要交换它们。这种交换是一种昂贵的操作,并且交换的总数对于评估算法的整体效率也将是很重要的。

Last updated