平均复杂度为O(n*log n)的:
归并排序、堆排序、快速排序。
快速排序的最差情况为O(n*n);
其他常见的为O(n*n);
排序效率与待排数组初始状况不敏感的有:归并排序、堆排序、选择排序。
稳定的排序:两个值相等的元素a与b,若排序前后a、b的相对位置不变,称为稳定的排序。
不稳定的排序:由上可得。
希尔排序
算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。冒泡排序
冒泡排序算法的运作如下:(从后往前)
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
各种排序代码实现
归并 排序
http://blog.csdn.net/chuchus/article/details/21822557
堆排序
http://blog.csdn.net/chuchus/article/details/39139531
快速排序