• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

一些排序算法及其时间复杂度

开发技术 开发技术 4小时前 1次浏览

稳定排序

冒泡排序:相邻两个元素比较   O(n^2)

插入排序:和当前位置的前一个元素进行比较,如果前一个元素比当前元素大,则后续进行调整,将前面的大元素不断向后移动,并找到合适的位置将当前元素插入进去。

最好情况  O(n) 最坏  O(n^2)

归并排序:不断折半分再合起来   O(n log 2n)

计数排序:一种特殊的桶排序   O(n+k)

基数排序:从最低位到最高位依次排序   O(s(n+k))(   n表示待排序列的规模,d表示待排序列的最大位数,k表示每一位数的范围,这也是一种时间换空间的算法

不稳定排序:

选择排序:指定位置的数和后面的数比较,交换次数比冒泡少  O(N^2)

堆排序:反复交换堆顶元素和末尾元素 O(n log n)

快速排序:设置好分界值,处理左侧和右侧   平均 O(n log n)最坏  O(n^2)

希尔排序:把记录按步长(最后一步步长必须为一)分组,对每组记录采用直接插入排序方法进行排序。


程序员灯塔
转载请注明原文链接:一些排序算法及其时间复杂度
喜欢 (0)