常用排序算法

稳定性分析

稳定排序算法不会在排序后改变相等键值记录间的相对次序。

849589-20180402133438219-1946132192


冒泡排序

交换逆序的相邻关键字

时间复杂度:$O(n^2)$

改进策略1:设置标志位,若某一轮没有发生交换,则排序结束 改进策略2:第i次遍历范围为0~N-i

849589-20171015223238449-2146169197

插入排序

讲一个记录插入到有序表中,在基本良序的表中性能更好。

时间复杂度:$O(n^2)$

849589-20171015225645277-1151100000

选择排序

第i次在 i~n的范围内寻找最小值,并放置在第i个位置处。

时间复杂度:$O(n^2)$

849589-20171015224719590-1433219824

希尔排序

1024555-20161128110416068-1421707828 849589-20180331170017421-364506073

归并排序

利用分治思想对两个良序数组合并。可以快速解决逆序对相关问题。

时间复杂度:$O(nlogn)$

空间复杂度:$O(n)$ 需要辅助空间帮助合并过程

849589-20171015230557043-37375010

堆排序

堆是一种特殊的完全二叉树

  • 大顶堆:父节点大于等于子节点
  • 小顶堆:父节点小于等于子节点 应用:$O(nlogk)$复杂度解决前k个最大值问题

快排

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。时间复杂度为O(nlogn) 应用:快速解决求第k大的值问题。

849589-20171015230936371-1413523412

Reference