一、概述

排序算法 时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 O(n²) O(n) O(n²) O(1) in-place 稳定
插入排序 O(n²) O(n) O(n²) O(1) in-place 稳定
希尔排序 O(n^(1.3—2)) O(n^(1.3)) O(n²) O(1) in-place 不稳定
选择排序 O(n²) O(n²) O(n²) O(1) in-place 稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) out-place 稳定
快速排序 O(n log n) O(n log n) O(n²) O(log n) in-place 不稳定
堆排序 O(n log n) O(n log n) O(n log n) O(1) in-place 不稳定
计数排序 O(n + k) O(n + k) O(n + k) O(k) out-place 稳定
桶排序 O(n + k) O(n + k) O(n²) O(n + k) out-place 稳定
基数排序 O(n * k) O(n * k) O(n * k) O(n * k) out-place 稳定

二、名词解释

  • 稳定性

    当前有数组[2, 1, 3, 3, 5]， 经过某算法排序后数组变得有序，其中存在相同的元素3，如果相同的两个元素3先后顺序没发送变化，当前使用的排序算法为稳定排序算法。

    例如：冒泡排序相同的元素是不发送交换的，所以冒泡排序是稳定排序算法。

  • 排序方式

    假设数组长度为n，当前排序算法需要另外再新建数组存放顺序的结果，这种方式为out-place。