admin管理员组文章数量:1530867
2024年5月5日发(作者：)
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象
是冒泡： 复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。
直接插入排序：O(n*n)
选择排序：O(n*n)
快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情
况下总是最好的。
归并排序：log2(n)*n
堆排序：log2(n)*n
希尔排序：算法的复杂度为n的1.2次幂
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：
首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即
k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或
最大值，那么他将变成交换法（由于使用了递归，情况更糟）。但是你认为这种情
况发生的几率有多大？？呵呵，你完全不必担心这个问题。实践证明，大多数的情
况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但
是通常情况下速度要慢 于快速排序（因为要重组堆）。
这几天笔试了好几次了，连续碰到一个关于常见排序算法稳定性判别的问题，往往
还是多选，对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目，当
然如果你笔试之前已经记住了数据结构书上哪些是稳定的，哪些不是稳定的，做起
来应该可以轻松搞定。
本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备
的。
首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相
等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形
式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。
其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，
然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排
序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相
同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素
交换的次数可能会少一些(个人感觉，没有证实)。
回到主题，现在分析一下常见的排序算法的稳定性，每个都给出简单的理由。
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元
素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会
再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面
的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有
改变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，
在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n
个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当
前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那
么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一
遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏
了，所以选择排序不是一个稳定的排序算法。
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚
开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾
版权声明：本文标题：各种排序方法总结 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1714884725a423866.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论