数据结构&算法排序技术

排序技术

排序是指以特定格式排列数据。排序算法指定了按特定顺序排列数据的方式。最常见的顺序是按数字顺序或字典顺序。排序的重要性在于，如果以排序方式存储数据，则可以将数据搜索优化到很高的水平。排序还用于以更具可读性的格式表示数据。以下是现实场景中排序的一些示例-

电话簿 - 电话簿存储按姓名排序的人员的电话号码，以便可以轻松搜索姓名。
字典 - 字典按字母顺序存储单词，因此搜索任何单词变得容易。

就地排序和非就地排序

排序算法可能需要一些额外的空间用于比较和临时存储少量数据元素。这些算法不需要任何额外的空间，并且排序发生在原位，例如在数组本身内。这称为就地排序。冒泡排序是就地排序的一个示例。但是，在某些排序算法中，程序需要的空间大于或等于要排序的元素。使用相等或更多空间的排序称为非就地排序。合并排序是非就地排序的一个示例。

稳定和不稳定排序

如果对内容进行排序后，排序算法没有更改它们出现的相似内容的顺序，则称为稳定排序。

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

当我们希望维持原始元素的序列时（例如在元组中），算法的稳定性至关重要。

自适应和非自适应排序算法

如果排序算法利用了要排序的列表中已经“排序”的元素，则称为自适应算法。也就是说，在排序时，如果源列表中已经有一些元素已经排序，则自适应算法将考虑到这一点，并且将尝试不对它们重新排序。非自适应算法是一种不考虑已排序元素的算法。他们试图迫使每个元素重新排序以确认其排序。

重要术语

在讨论排序技术时，通常会创造一些术语，这里是对它们的简要介绍-

递增升序

如果连续元素大于前一个元素，则值序列被认为是升序。例如，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的情况下）但不小于前一个元素。