各种排序算法的稳定性和时间复杂度小结VIP专享

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法， 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 冒泡法： 这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： 复杂度为 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 位置前。 其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也...