You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.
常用排序算法

常用排序算法

. 3 min read

稳定性分析

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


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