排序算法的稳定性-yiteyi-C++库

当我们有可能具有重复键的键值对时（比如人名作为键，他们的细节作为值），稳定性主要很重要。我们希望按键对这些对象进行排序。

null

这是怎么一回事？ 如果两个具有相等键的对象在排序输出中的顺序与它们在待排序的输入数组中的顺序相同，则称排序算法是稳定的。

从形式上讲，稳定性可以定义为：，让 $A$ 做一个数组，让 $<$ 在元素上是严格的弱序 $A$ . 排序算法是稳定的，如果- $i < j::and::A[i]equiv A[j]::implies::pi (i) < pi (j)$ 哪里 $pi$ 是排序排列（排序移动） $A[i]$ 定位 $pi(i)$ ) 非正式地说，稳定性意味着对等元素在排序后保留其相对位置。

stability-sorting

我们关心像整数数组这样的简单数组吗？ 当相等的元素不可区分时，比如整数，或者更一般地说，任何以整个元素为关键的数据，稳定性不是问题。如果所有钥匙都不同，稳定性也不是问题。

这是一个有用的例子 考虑下面的学生姓名数据集及其相应的类节。

$(Dave, A) (Alice, B) (Ken, A) (Eric, B) (Carol, A)$

如果我们只根据名称对这些数据进行排序，那么生成的数据集也不太可能按照部分进行分组。

$(Alice, B) (Carol, A) (Dave, A) (Eric, B) (Ken, A)$

因此，我们可能需要再次排序，以获得学生名单的部分。但是这样做的时候，如果排序算法不稳定，我们可能会得到这样的结果-

$(Carol, A) (Dave, A) (Ken, A)(Eric, B)(Alice, B)$

数据集现在是按节排序的，但不是按名称排序的。在名称排序数据集中，元组 $(Alice, B)$ 以前 $(Eric, B)$ ，但由于排序算法不稳定，相对顺序丢失。另一方面，如果我们使用稳定的排序算法，结果会是-

$(Carol, A) (Dave, A) (Ken, A)(Alice, B)(Eric, B)$

在这里，不同元组之间的相对顺序保持不变。在这种情况下，相对顺序可能会保持在不稳定的排序中，但这是极不可能的。

哪些排序算法是稳定的？ 有些排序算法本质上是稳定的，例如气泡排序 , 插入排序 , 合并排序 , 计数排序等基于比较的稳定排序，如合并排序和插入排序，通过确保- 要素 $A[j]$ 先于 $A[i]$ 如果且仅当 $A[j] < A[i]$ 这里i，j是指数和 $i < j$ . 自从 $i<j$ ，相对顺序得以保留 $if A[i]equiv A[j]$ 即 $A[i]$ 先于 $A[j]$ . 其他非基于比较的分类，如计数排序通过确保按相反顺序填充排序的数组来保持稳定性，以便具有等效键的元素具有相同的相对位置。比如基数排序依赖于另一类，唯一的要求是另一类应该是稳定的。