算法笔记--八个常见排序算法总结


一、 分类描述

1. 插入排序

          直接插入排序:算法简单,稳定,适用于数据量小的情况

         希尔排序:直接插入排序的改进版,不稳定,对于待排序序列的不同情况效率相近

2. 交换排序

          冒泡排序:算法简单,稳定,在数据基本有序的情况下效率较高

         快速排序:算法效率高,不稳定,需要额外的辅助空间

3. 选择排序

         直接选择排序:任何情况时间复杂度均为O(n^2),不稳定,其优势在于交换次数少

         堆排序:不稳定,对序列的原始顺序不敏感,适用于数据量大的情况

4. 归并排序

          分治策略,稳定,适用于待排序列整体无序、部分有序的情况,需要额外的辅助空间

5. 基数排序

          稳定;适用范围有限;当数据位数较小时,时间复杂度近似为O(n),效率高于其它的稳定性排序算法

二、总结比较表

类别

排序方法

时间复杂度

空间复杂度

稳定性

复杂性

最好

最坏

平均

插入排序

直接插入

O(n)

O(n^2)

O(n^2)

O(1)

O

简单

希尔排序

O(n^1.3)

O(n^2)

O(n^1.x)

O(1)

X

较复杂

交换排序

冒泡排序

O(n)

O(n^2)

O(n^2)

O(1)

O

简单

快速排序

O(nlogn)

O(n^2)

O(nlogn)

O(logn)

X

较复杂

选择排序

直接选择

O(n^2)

O(n^2)

O(n^2)

O(1)

X

简单

堆排序

O(nlogn)

O(nlogn)

O(nlogn)

O(1)

X

较复杂

 

归并排序

O(nlogn)

O(nlogn)

O(nlogn)

O(n)

O

较复杂

 

基数排序

O(d(n+r))

O(d(n+r))

O(d(n+r))

O(n+r)

O

较复杂


上一篇:【算法小总结】二分图的最大独立集


下一篇:基于PAI 10分钟搭建一个简单推荐系统