常见排序算法的稳定性分析

逃离我推掉我的手 2023-06-02 09:17 68阅读 0赞

## 一、不稳定排序算法有哪些 ##

### 1、堆排序 ###

### 2、希尔排序 ###

### 3、快速排序 ###

### 4、选择排序 ###

![1731684-20190823022203493-1476798749.png][]

口诀：**一堆**（堆）**希尔**（希尔）**快**（快速）**选**（选择）

## 二、常见排序算法稳定性分析 ##

### 1、堆排序稳定性分析 ###

我们知道堆的结构是节点i的孩子为 2\*i 和 2\*i+1 节点，大顶堆要求父节点大于等于其 2 个子节点，小顶堆要求父节点小于等于其 2 个子节点。

在一个长为 n 的序列，堆排序的过程是从第 n/2 开始和其子节点共 3 个值选择最大（大顶堆）或者最小（小顶堆），这 3 个元素之间的选择当然不会破坏稳定性。

但当为 n/2-1, n/2-2, ...1 这些个父节点选择元素时，就会破坏稳定性。

有可能第 n/2 个父节点交换把后面一个元素交换过去了，而第 n/2-1 个父节点把后面一个相同的元素没有交换，那么这 2 个相同的元素之间的稳定性就被破坏了。

所以，堆排序不是稳定的排序算法。

### 2、希尔排序 ###

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；

当元素基本有序时，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比 O(N^2) 好一些。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，

但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。

所以 shell 排序是不稳定的排序算法。

### 3、快速排序 ###

快速排序有两个方向，左边的 i 下标一直往右走（当条件 a\[i\] <= a\[center\_index\] 时），其中 center\_index 是中枢元素的数组下标，一般取为数组第 0 个元素。

而右边的 j 下标一直往左走（当 a\[j\] > a\[center\_index\] 时）。

如果 i 和 j 都走不动了，i <= j, 交换 a\[i\] 和 a\[j\]，重复上面的过程，直到 i>j。交换 a\[j\] 和 a\[center\_index\]，完成一趟快速排序。

在中枢元素和 a\[j\] 交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11

现在中枢元素 5 和 3（第 5 个元素，下标从 1 开始计）交换就会把元素 3 的稳定性打乱。

所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和 a\[j\] 交换的时刻。

### 4、选择排序 ###

选择排序即是给每个位置选择待排序元素中当前最小的元素。比如给第一个位置选择最小的，在剩余元素里面给第二个位置选择次小的，

依次类推，直到第 n-1 个元素，第 n 个元素不用选择了，因为只剩下它一个最大的元素了。

那么，在一趟选择时，如果当前锁定元素比后面一个元素大，而后面较小的那个元素又出现在一个与当前锁定元素相等的元素后面，那么交换后位置顺序显然改变了。

举个例子：序列5 8 5 2 9， 我们知道第一趟选择第 1 个元素 5 会与 2 进行交换，那么原序列中两个5的相对先后顺序也就被破坏了。

所以选择排序不是一个稳定的排序算法。

### 5、冒泡排序 ###

冒泡排序就是把小的元素往前调（或者把大的元素往后调）。注意是相邻的两个元素进行比较，而且是否需要交换也发生在这两个元素之间。

所以，如果两个元素相等，我想你是不会再无聊地把它们俩再交换一下。

如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个元素相邻起来，最终也不会交换它俩的位置，所以相同元素经过排序后顺序并没有改变。

所以冒泡排序是一种稳定排序算法。

### 6、插入排序 ###

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有 1 个元素，也就是第一个元素（默认它有序）。

比较是从有序序列的末尾开始，也就是把待插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面。

否则一直往前找直到找到它该插入的位置。如果遇见一个与插入元素相等的，那么把待插入的元素放在相等元素的后面。

所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序仍是排好序后的顺序，所以插入排序是稳定的。

### 7、归并排序 ###

归并排序是把序列递归地分成短序列，递归出口是短序列只有 1 个元素（认为直接有序）或者 2 个序列（1 次比较和交换)，

然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。

可以发现，在 1 个或 2 个元素时，1 个元素不会交换，2 个元素如果大小相等也没有人故意交换，这不会破坏稳定性。

那么，在短的有序序列合并的过程中，稳定是是否受到破坏？

没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。

所以，归并排序也是稳定的排序算法。

### 8、基数排序 ###

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序结果就是高优先级高的在前，高优先级相同的情况下低优先级高的在前。

基数排序基于分别排序，分别收集，所以其是稳定的排序算法。

转载于:https://www.cnblogs.com/Leophen/p/11397731.html

[1731684-20190823022203493-1476798749.png]: /images/20230601/2f560119d97444be816d93e690fe7203.png

发表评论取消回复

表情：

评论列表（有 0 条评论，68人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构：排序算法的稳定性分析

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXz...

桃扇骨/ 2024年04月17日 05:25/ 0 赞/ 76 阅读

相关什么是排序算法的稳定性？

什么是排序算法的稳定性？ `今天来了解一下排序算法的稳定性的定义和一些常见排序算法的稳定性，一起来看看吧！` 我们知道排序算法有时间、空间复杂度，那稳定性是什么意思呢

忘是亡心i/ 2024年03月30日 15:37/ 0 赞/ 71 阅读

相关排序算法之稳定性分析

首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原

左手的ㄟ右手/ 2024年02月18日 23:47/ 0 赞/ 55 阅读

相关几种常见排序算法的复杂度和稳定性

![format_png][] [format_png]: /images/20230528/5c0cc13c615d457791c48e0c65958b03.png

缺乏、安全感/ 2023年07月24日 14:48/ 0 赞/ 17 阅读

相关常见排序算法的稳定性分析

一、不稳定排序算法有哪些 1、堆排序 2、希尔排序 3、快速排序 4、选择排序 ![1731684-20190823022203493-14767

逃离我推掉我的手/ 2023年06月02日 09:17/ 0 赞/ 69 阅读

相关排序算法的稳定性

稳定：如果a原本在b的前面，而a=b，排序后a仍在b的前面。不稳定性：如果a原本在b的前面，而a=b，排序后a可能在b的后面。插入排

Bertha 。/ 2022年12月04日 01:04/ 0 赞/ 165 阅读

相关 java排序的稳定性_Java排序（二）排序算法的稳定性

排序算法的稳定性概念\[1\] 如果 a = b， a原本在b的前面，排序之后， a仍然在b的前面，那么这个排序算法就是稳定的。反之，就是不稳定的排序算法。背景：“

我就是我/ 2022年11月03日 00:54/ 0 赞/ 196 阅读

相关几种排序算法的稳定性比较

排序算法的稳定性，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。例如，如果Ai=Aj，原来在位置前，排序后Ai还是要在Aj位置前

朱雀/ 2022年06月09日 12:26/ 0 赞/ 232 阅读

相关排序算法的稳定性及其意义

稳定性的定义假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排

╰+攻爆jí腚メ/ 2022年05月12日 06:10/ 0 赞/ 212 阅读

相关排序算法稳定性

排序算法稳定性判定方法：假定在待排序的元素中，存在2个及以上相同的元素，若经过排序，这些元素的相对顺序保持不变，即在原序列中，r\[i\]=r\[j\]，且r\[i\]在r

今天药忘吃喽~/ 2022年01月15日 12:59/ 0 赞/ 235 阅读