各种常用排序算法

类别

排序方法

时间复杂度

空间复杂度

稳定性

复杂性

特点

最好

平均

最坏

辅助存储

简单

插入

排序

直接插入

Insert

O(N)

O(N²)

O(N²)

O(1)

稳定

简单 

希尔排序

Shell

O(N)

O(N^1.3)

O(N²)

O(1)

不稳定

复杂

选择

排序

直接选择

Select

O(N)

O(N²)

O(N²)

O(1)

不稳定

 按理说平均复杂度和最坏复杂度相同是稳定排序。但是：序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

堆排序

Heap

O(N*log₂N)

O(N*log₂N)

O(N*log₂N)

O(1)

不稳定

复杂

 堆排序跟直接选择类似

交换

排序

冒泡排序

Buble

O(N)

O(N²)

O(N²)

O(1)

稳定

简单

1、冒泡排序是一种用时间换空间的排序方法，n小时好
2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级
3、最好的情况是数据本来就有序，复杂度为O(n)

快速排序

Quick

O(N*log₂N)

O(N*log₂N) 

O(N²)

O(log₂n)~O(n) 

不稳定

复杂

1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。
2、划分之后一边是一个，一边是n-1个，
这种极端情况的时间复杂度就是O(N^2)
3、最好的情况是每次都能均匀的划分序列，O(N*log₂N)

归并排序

Merge

O(N*log₂N) 

O(N*log₂N) 

O(N*log₂N) 

O(n)

稳定

复杂

1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。

基数排序

Radix

O(d(r+n))

O(d(r+n))

O(d(r+n))

O(rd+n)

稳定

复杂

注：r代表关键字基数，d代表长度，n代表关键字个数