Data Structures Algorithms 简明教程
Data Structures - Sorting Techniques
排序是指按照特定格式排列数据。排序算法规定了以特定顺序排列数据的方式。最常见的顺序是按数字或词法顺序。
对于按升序排列的数据进行数据搜索可以优化到很高的级别，因此排序的重要性在于数据是以按升序排列的方式存储。排序还用于以更易于读取的格式表示数据。以下是现实场景中排序的一些示例 -
-
Telephone Directory - 电话号码簿按姓名对人们的电话号码进行排序，以便可以轻松地搜索姓名。
-
Dictionary - 字典按字母顺序存储单词，以便轻松搜索任何单词。
In-place Sorting and Not-in-place Sorting
排序算法可能需要一些额外的空间来比较和临时存储几个数据元素。这些算法不需要任何额外的空间，并且排序被认为是就地进行，例如，在数组本身内。这被称为 in-place sorting 。冒泡排序是就地排序的一个示例。
然而，在一些排序算法中，该程序需要相对于要排序的元素而言更大或相等的空间。使用相等或更多空间的排序称为 not-in-place sorting 。归并排序是不就地的排序的一个示例。
Stable and Not Stable Sorting
如果排序算法在对内容排序后，不更改相似内容出现的顺序，则称为 stable sorting 。
如果排序算法在对内容排序后，更改相似内容出现的顺序，则称为 unstable sorting 。
当我们希望保持原始元素的顺序（例如在元组中）时，算法的稳定性很关键。
Adaptive and Non-Adaptive Sorting Algorithm
如果排序算法利用待排序列表中的“已排序”元素，则称该算法是自适应的。也就是说，在排序时如果源列表已对某些元素进行排序，自适应算法将对此加以考虑，并将尝试不重新排序这些元素。
非自适应算法是不考虑已排序元素的算法。它们会尝试强制对每个元素重新排序以确认其排序性。
Important Terms
在讨论排序技术时，通常会创造一些术语，这里是对它们的简要介绍 -
Non-Increasing Order
如果连续元素小于或等于其在序列中的前一个元素，则称值按 non-increasing order 排列。当序列包含重复值时，出现此顺序。例如，9、8、6、3、3、1 按非递减顺序排列，因为每个下一个元素都小于或等于（在 3 的情况下）但并不大于任何前一个元素。