5.6. 排序¶
5.6. Sorting
排序是将集合中的元素按某种顺序排列的过程。例如，一个单词列表可以按字母顺序或长度排序。一个城市列表可以按人口、面积或邮政编码排序。我们已经看到了一些能够受益于有序列表的算法（回忆一下最终的字谜例子和二分查找）。
已经开发并分析了许多排序算法。这表明排序是计算机科学中一个重要的研究领域。对大量项目进行排序可能会消耗大量计算资源。与搜索一样，排序算法的效率与处理的项目数量有关。对于小型集合，复杂的排序方法可能不值得使用，开销可能过高。另一方面，对于较大的集合，我们希望尽可能利用各种改进。在本节中，我们将讨论几种排序技术，并比较它们的运行时间。
在讨论具体算法之前，我们应该考虑用于分析排序过程的操作。首先，需要比较两个值以确定哪个更小（或更大）。为了对集合进行排序，需要有一些系统的方法来比较值，以查看它们是否有序。比较的总次数将是衡量排序过程最常见的方法。其次，当值相对于彼此的位置不正确时，可能需要交换它们。这种交换是一个代价高昂的操作，总交换次数对于评估算法的整体效率也很重要。
Sorting is the process of placing elements from a collection in some kind of order. For example, a list of words could be sorted alphabetically or by length. A list of cities could be sorted by population, by area, or by zip code. We have already seen a number of algorithms that were able to benefit from having a sorted list (recall the final anagram example and the binary search).
There are many, many sorting algorithms that have been developed and analyzed. This suggests that sorting is an important area of study in computer science. Sorting a large number of items can take a substantial amount of computing resources. Like searching, the efficiency of a sorting algorithm is related to the number of items being processed. For small collections, a complex sorting method may be more trouble than it is worth. The overhead may be too high. On the other hand, for larger collections, we want to take advantage of as many improvements as possible. In this section we will discuss several sorting techniques and compare them with respect to their running time.
Before getting into specific algorithms, we should think about the operations that can be used to analyze a sorting process. First, it will be necessary to compare two values to see which is smaller (or larger). In order to sort a collection, it will be necessary to have some systematic way to compare values to see if they are out of order. The total number of comparisons will be the most common way to measure a sort procedure. Second, when values are not in the correct position with respect to one another, it may be necessary to exchange them. This exchange is a costly operation and the total number of exchanges will also be important for evaluating the overall efficiency of the algorithm.
创建日期: 2024年9月9日