(排序算法复杂度.docVIP

各种排序算法的稳定性和时间复杂度小结 交换排序、选择排序、希尔shell排序、快速排序、堆排序不是稳定的排序算法， 冒泡排序、插入排序、基数排序和归并排序是稳定的排序算法。 排序法 平均时间 最差情形 稳定度 额外空间 备注 冒泡 O(n2) O(n2) 稳定 O(1) n小时较好 交换 O(n2) O(n2) 不稳定 O(1) n小时较好 选择 O(n2) O(n2) 不稳定 O(1) n小时较好 插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好 基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)， R是基数(个十百) Shell O(nlogn) O(ns) 1s2 不稳定 O(1) s是所选分组 快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好 归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好 堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好 实践证明，大多数的情况，快速排序总是最好的。 如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。 首先我们考虑最理想的情况 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都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。 ?????首先，排序算法的稳定性大家应该都知道，通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。 ???? 其次，说一下稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就 是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换 的次数可能会少一些(个人感觉，没有证实)。 (1)冒泡排序 ????冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无 聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，所以冒泡排序是一种稳定排序算法。 (2)选择排序 ????选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。 (3)插入排序????插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳 定的。 (4)快速排序??? 快速排序有两个方向，左边的i下标一直往右走，当a[i] = a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] a[center_index]。如果i和j都走不动了，i = j, 交换a[i]和a[j],重复上面的过程，直到ij。 交换a[j]和a[ce