目录
- 1. 排序算法的介绍
- 2. 各排序算法的时间复杂度情况
1. 排序算法的介绍
定义：排序是将一组数据，依指定的顺序进行排列的过程
排序的分类：
- 内部排序：将需要处理的所有数据都加载到内部存储器中进行排序
- 插入排序(直接插入排序、希尔排序)
- 选择排序(简单选择排序、堆排序)
- 交换排序(冒泡排序、快速排序)
- 归并排序
- 基数排序
- 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行 排序
2. 各排序算法的时间复杂度情况
排序法平均时间最好情形最差情形空间复杂度稳定性排序方式性能测试备注冒泡
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
)
O(n)
O(n)
O
(
n
2
)
O(n^2)
O(n2)O(1)稳定In-place对于8万个元素的数列，用时16秒n小较好选择
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
2
)
O(n^2)
O(n2)O(1)不稳定In-place对于8万个元素的数列，用时3秒n小较好插入
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
)
O(n)
O(n)
O
(
n
2
)
O(n^2)
O(n2)O(1)稳定In-place对于8万个元素的数列，用时5秒大部分已排序时较好希尔Shell
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
s
)
O(n^s)
O(ns) 1 < s < 2O(1)不稳定In-place交换法对于8万个元素的数列，用时16秒；移动法对于8万个元素的数列，用时1秒s是所选分组快速
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)不稳定In-place对于8万个元素的数列，用时不到1秒；80万个元素的数列，用时1秒n大较好归并
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)O(1)稳定Out-place对于8万个元素的数列，用时不到1秒；80万个元素的数列，用时1秒n大较好基数
O
(
l
o
g
R
B
)
O(log_RB)
O(logRB)
O
(
l
o
g
R
B
)
O(log_RB)
O(logRB)O(n)稳定Out-place对于80万个元素的数列，用时不到1秒；800万个元素的数列，用时1秒；8000万个元素的数列，直接内存溢出B是真数(0-9)，R是基数(个十百)堆
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)O(1)不稳定In-place800万个元素的数列，用时3秒n大较好交换
O
(
n
2
)
O(n^2)
O(n2)
O
(
n
2
)
O(n^2)
O(n2)O(1)不稳定n小较好
说明：
- 稳定性是指当两个相同的元素，进行排序后，它们的次序并不会发现变化
- In-place表示为了完成排序，不新建其它临时数组；Out-place表示新建其它临时数组
