菜鸟笔记
提升您的技术认知

经典排序算法

阅读 : 2429

排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则称为外排序。

我们通常所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。

排序算法大体可分为两种:

一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序选择排序插入排序,归并排序,堆排序,快速排序等。

另一种是非比较排序,时间复杂度可以达到O(n),主要有:计数排序,基数排序,桶排序等。

内排序有可以分为以下几类:

(1)插入排序:直接插入排序、二分法插入排序、希尔排序

(2)选择排序:直接选择排序、堆排序

(3)交换排序:冒泡排序、快速排序

(4)归并排序

(5)基数排序

排序方法 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性 复杂性
插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
希尔排序 O(nlog2n) O(n2) O(n1.3) O(1) 不稳定 较复杂
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 较复杂
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂

排序算法专业术语解释

1、稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 仍然在 b 的前面,则为稳定排序。

2、非稳定排序:如果 a 原本在 b 的前面,且 a == b,排序之后 a 可能不在 b 的前面,则为非稳定排序。

3、原地排序:原地排序就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4、非原地排序:需要利用额外的数组来辅助排序。

5、时间复杂度:一个算法执行所消耗的时间。

6、空间复杂度:运行完一个算法所需的内存大小。