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

你的名字 2022-04-16 02:11 243阅读 0赞

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

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

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

咋看上面的文字有点抽象，我们来举个栗子。  
![在这里插入图片描述][2018111516241030.png]

有一组待排序的序列：

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

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

![在这里插入图片描述][20181115162443892.png]

为了方便区分和理解，我们暂且把 arr\[2\] 中的 56 称为 A，arr\[4\] 中的 56 称为 B，效果如下  
![在这里插入图片描述][20181115162504684.png]  
那单从 A 和 B 的相对前后位置来说，经过排序后，就会有两种可能的结果。

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

![在这里插入图片描述][20181115162539470.png]  
A、B 的相对位置没变。

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

*2* A 被排到 B 后面了，即原来 arr\[2\] 的 56 被排到了 arr\[4\] 的 56 后面  
![在这里插入图片描述][20181115162601476.png]  
原来的 A、B 的相对位置改变了。

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

![在这里插入图片描述][20181115162618239.png]  
简而言之，原来相同记录的相对（前后）位置，经过排序后，如果相对位置不改变，则该排序算法稳定，否则不稳定。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01PRVNFQ1NETg_size_16_color_FFFFFF_t_70]

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

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

[2018111516241030.png]: /images/20220416/5de49687cca443cca8c09ad681bec66a.png
[20181115162443892.png]: /images/20220416/9ad635e13b4944faa00f00af109abf51.png
[20181115162504684.png]: /images/20220416/ea03421aa4d7477db7f96e37fbe7bf5e.png
[20181115162539470.png]: /images/20220416/1b8d6d7195b94ab59c86a936543c0de7.png
[20181115162601476.png]: /images/20220416/13c6719cd1ba4bc08f9099d17b083429.png
[20181115162618239.png]: /images/20220416/471cbffdcd84462a803eff2cbb039915.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01PRVNFQ1NETg_size_16_color_FFFFFF_t_70]: /images/20220416/d9abf54570894f43859dc81ea058ccb3.png