数据结构 - 排序技术

排序是指以特定格式排列数据。排序算法指定以特定顺序排列数据的方式。最常见的顺序是数值顺序或字典顺序。

排序的重要性在于，如果数据以排序的方式存储，则可以将数据搜索优化到非常高的水平。排序还用于以更易读的格式表示数据。以下是现实生活中排序的一些示例：

原地排序和非原地排序

排序算法可能需要一些额外的空间来比较和临时存储少量数据元素。这些算法不需要任何额外的空间，并且据说排序是在原地发生的，或者例如，在数组本身内。这称为原地排序。冒泡排序是原地排序的一个例子。

但是，在某些排序算法中，程序需要大于或等于被排序元素的空间。使用等于或更多空间的排序称为非原地排序。归并排序是非原地排序的一个例子。

如果排序算法在排序内容后不更改其出现顺序的相似内容，则称为稳定排序。

如果排序算法在排序内容后更改其出现顺序的相似内容，则称为不稳定排序。

当我们希望维护原始元素的顺序（例如元组）时，算法的稳定性很重要。

如果排序算法利用要排序的列表中已经“排序”的元素，则称该排序算法为自适应的。也就是说，在排序时，如果源列表中有一些元素已经排序，则自适应算法将考虑这一点，并会尝试不重新排序它们。

非自适应算法是不考虑已经排序的元素的算法。它们试图强制重新排序每个元素以确认其排序性。

在讨论排序技术时，通常会创造一些术语，以下是它们的简要介绍：

如果后续元素大于前一个元素，则称一系列值处于升序。例如，1、3、4、6、8、9 按升序排列，因为每个后续元素都大于前一个元素。

如果后续元素小于当前元素，则称一系列值处于降序。例如，9、8、6、4、3、1 按降序排列，因为每个后续元素都小于前一个元素。

如果后续元素小于或等于序列中其前一个元素，则称一系列值处于非递增序。当序列包含重复值时，会出现此顺序。例如，9、8、6、3、3、1 按非递增序排列，因为每个后续元素都小于或等于（对于 3）但不大于任何前一个元素。

如果后续元素大于或等于序列中其前一个元素，则称一系列值处于非递减序。当序列包含重复值时，会出现此顺序。例如，1、3、3、6、8、9 按非递减序排列，因为每个后续元素都大于或等于（对于 3）但不小于前一个元素。

有几种可用的排序技术来对各种数据结构的内容进行排序。以下是一些：

打印页面