排序算法比较 时间复杂度 稳定性描述

冒泡法：  
这是最原始，也是众所周知的最慢的算法了。
复杂度为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)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。