【数据结构】常见排序算法的比较

【数据结构】常见排序算法的比较 2022-07-26 491

前言

对于各种排序算法的性能我们可以从时间复杂度、空间复杂度、特殊情况和稳定性四个方面来比较。其中特殊情况是指当序列为有序时，对排序算法复杂度的影响。

一、各种排序算法比较

排序算法时间复杂度空间复杂度序列有序稳定性直接插入排序 O(n^2) O(1) O(n) 稳定希尔排序 O(n^1.3) O(1) / 不稳定冒泡排序 O(n^2) O(1) O(n) 稳定快速排序 O(nlog2 n) O(log2 n) O(n^2) 不稳定简单选择排序 O(n^2) O(1) O(n^2) 不稳定堆排序 O(nlog2 n) O(1) O(nlog2 n) 不稳定归并排序 O(nlog2 n) O(n) O(nlog2 n) 稳定基数排序 O(k(m+n)) O(n+m) O(k(m+n)) 稳定

选择排序算法时一般遵循的原则：排序规模不大，用直接插入排序、简单选择排序、冒泡排序均可，虽然其时间复杂度稍逊于快速排序等算法。但其实现简单，在数据量较小时性能的差距体现不明显。当排序规模很大且对稳定性有要求时，可以采用归并排序，前提是有足够的辅助空间。当排序规模很大而关键字位数较小时，可以采用基数排序，速度有保证且稳定。’

免费搭建微信查券返利机器人来轻松赚佣金