Question

5.6.排序

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

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

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