Data Structures Algorithms 简明教程
Data Structures - Sorting Techniques
排序是指按照特定格式排列数据。排序算法规定了以特定顺序排列数据的方式。最常见的顺序是按数字或词法顺序。
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.
对于按升序排列的数据进行数据搜索可以优化到很高的级别，因此排序的重要性在于数据是以按升序排列的方式存储。排序还用于以更易于读取的格式表示数据。以下是现实场景中排序的一些示例 -
The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Following are some of the examples of sorting in real-life scenarios −
-
Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily.
-
Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy.
In-place Sorting and Not-in-place Sorting
排序算法可能需要一些额外的空间来比较和临时存储几个数据元素。这些算法不需要任何额外的空间，并且排序被认为是就地进行，例如，在数组本身内。这被称为 in-place sorting 。冒泡排序是就地排序的一个示例。
Sorting algorithms may require some extra space for comparison and temporary storage of few data elements. These algorithms do not require any extra space and sorting is said to happen in-place, or for example, within the array itself. This is called in-place sorting. Bubble sort is an example of in-place sorting.
然而，在一些排序算法中，该程序需要相对于要排序的元素而言更大或相等的空间。使用相等或更多空间的排序称为 not-in-place sorting 。归并排序是不就地的排序的一个示例。
However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting.
Stable and Not Stable Sorting
如果排序算法在对内容排序后，不更改相似内容出现的顺序，则称为 stable sorting 。
If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is called stable sorting.
如果排序算法在对内容排序后，更改相似内容出现的顺序，则称为 unstable sorting 。
If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is called unstable sorting.
当我们希望保持原始元素的顺序（例如在元组中）时，算法的稳定性很关键。
Stability of an algorithm matters when we wish to maintain the sequence of original elements, like in a tuple for example.
Adaptive and Non-Adaptive Sorting Algorithm
如果排序算法利用待排序列表中的“已排序”元素，则称该算法是自适应的。也就是说，在排序时如果源列表已对某些元素进行排序，自适应算法将对此加以考虑，并将尝试不重新排序这些元素。
A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted' elements in the list that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive algorithms will take this into account and will try not to re-order them.
非自适应算法是不考虑已排序元素的算法。它们会尝试强制对每个元素重新排序以确认其排序性。
A non-adaptive algorithm is one which does not take into account the elements which are already sorted. They try to force every single element to be re-ordered to confirm their sorted ness.
Important Terms
在讨论排序技术时，通常会创造一些术语，这里是对它们的简要介绍 -
Some terms are generally coined while discussing sorting techniques, here is a brief introduction to them −
Increasing Order
如果连续元素大于前一个元素，则称值序列按 increasing order 排列。例如，1、3、4、6、8、9 按升序排列，因为每个下一个元素都大于前一个元素。
A sequence of values is said to be in increasing order, if the successive element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater than the previous element.
Decreasing Order
如果连续元素小于当前元素，则称值按 decreasing order 排列。例如，9、8、6、4、3、1 按降序排列，因为每个下一个元素都小于前一个元素。
A sequence of values is said to be in decreasing order, if the successive element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than the previous element.
Non-Increasing Order
如果连续元素小于或等于其在序列中的前一个元素，则称值按 non-increasing order 排列。当序列包含重复值时，出现此顺序。例如，9、8、6、3、3、1 按非递减顺序排列，因为每个下一个元素都小于或等于（在 3 的情况下）但并不大于任何前一个元素。
A sequence of values is said to be in non-increasing order, if the successive element is less than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less than or equal to (in case of 3) but not greater than any previous element.
Non-Decreasing Order
如果连续元素大于或等于其在序列中的前一个元素，则称值按 non-decreasing order 排列。当序列包含重复值时，出现此顺序。例如，1、3、3、6、8、9 按非递增顺序排列，因为每个下一个元素都大于或等于（在 3 的情况下）但并不小于前一个元素。
A sequence of values is said to be in non-decreasing order, if the successive element is greater than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is greater than or equal to (in case of 3) but not less than the previous one.
有几种排序技术可用于对各种数据结构的内容进行排序。以下是一些 -
There are several sorting techniques available to sort the contents of various data structures. Following are some of those −