312 字

2 分钟

各种排序方法比较

2020-11-06

各种排序方法比较#

时间复杂度#

排序方法	平均情况	最好情况	最坏情况	辅助空间
直接插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$
希尔排序	$O(n \log_2 n) - O(n^2)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$
快速排序	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n^2)$	$O(\log_2 n)-O(n)$
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$
堆排序	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(1)$
归并排序	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n \log_2 n)$	$O(n)$
基数排序	$O(d(n+m))$	$O(d(n+m))$	$O(d(n+m))$	$O(m)$

【住】：基数排序的 d 为待排序记录的长度或关键码个数，m 为关键码的取值范围

稳定性#

稳定性指关键字相等的记录在排序后仍保持原来的相对顺序。以下分类针对这些算法的常规实现：

稳定排序：直接插入排序、冒泡排序（也称起泡排序）、归并排序、LSD 基数排序。
不稳定排序：希尔排序、快速排序、堆排序、简单选择排序。

冒泡排序只交换逆序的相邻元素；归并排序遇到相等关键字时优先取左侧元素；LSD 基数排序每一趟按位排序都需保持稳定。这些实现条件决定了最终的稳定性。

参考：Algorithms, 4th Edition 排序对照表、LSD 基数排序实现。

原文链接：CSDN

各种排序方法比较

https://blog.homura.work/posts/csdn/109537615/

作者

HMT

发布于

2020-11-06

许可协议

CC BY-NC-SA 4.0

基数排序-最低位优先法

各种排序方法比较

时间复杂度