怎样的排序算法才算稳定？

相信很多程序猿伙伴都会有意或无意用到算法，特别是排序算法，而排序算法则会涉及稳定性，那怎样的排序算法才算稳定呢？

根据百度百科给出对排序算法稳定性的简单描述，假定在待排序的记录序列中，存在多个具有相同的关键字的记录，经过排序，这些记录的相对次序保持不变。

即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的，否则称为不稳定的。

咋看上面的文字有点抽象，我们来举个栗子。

有一组待排序的序列：

int arr[] = {43,56,34,56,67,2};

其中，arr[2] 与 arr[4] 值都是 56 ，它们相等。

为了方便区分和理解，我们暂且把 arr[2] 中的 56 称为 A，arr[4] 中的 56 称为 B，效果如下

那单从 A 和 B 的相对前后位置来说，经过排序后，就会有两种可能的结果。

1     A 仍然排在 B 前面，即原来 arr[2] 的 56 仍然排在 arr[4] 的 56 前面。

A、B 的相对位置没变。

经过某种排序算法排序后，结果像 1 中所述，那么称这种排序算法是稳定的。

2      A 被排到 B 后面了，即原来 arr[2] 的 56 被排到了 arr[4] 的 56 后面

原来的 A、B 的相对位置改变了。

经过某种排序算法排序后，结果像 2 中所述，那么称这种排序算法是不稳定的。

简而言之，原来相同记录的相对（前后）位置，经过排序后，如果相对位置不改变，则该排序算法稳定，否则不稳定。

那常用的排序算法中，哪些是稳定的排序算法，哪些是不稳定呢？我做一个简单的思维导图。

但是要注意，排序算法是否稳定不是绝对的，排序算法是否为稳定的是由具体算法（代码）决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

本文章首发于公众号「MoTec」，公众号定期特别推送 Java、Python 干货、一起讨论技术、思维认知、投资理财；共享网络资源，分享个人所知一切，一起成长、To Be Better。