排序算法 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(n²) O(n) O(1) 稳定
直接选择排序 O(n²) O(n²) O(n) O(1) 不稳定
直接插入排序 O(n²) O(n²) O(n) O(1) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
希尔排序 O(nlogn) O(ns) O(n) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
计数排序 O(n+k) O(n+k) O(n+k) O(n+k) 稳定
基数排序 O(N*M) O(N*M) O(N*M) O(M) 稳定

辅助记忆

  • 时间复杂度记忆-

  • 冒泡、选择、直接 排序需要两个for循环,每次只关注一个元素,平均时间复杂度为O(n²))(一遍找元素O(n),一遍找位置O(n))

  • 快速、归并、希尔、堆基于二分思想,log以2为底,平均时间复杂度为O(nlogn)(一遍找元素O(n),一遍找位置O(logn))

  • 稳定性记忆-“快希选堆”(快牺牲稳定性)

  • 排序算法的稳定性:排序前后相同元素的相对位置不变,则称排序算法是稳定的;否则排序算法是不稳定的。

nlog(n)

代表执行了n次 [公式] 的操作,所以理解了log(n),就理解了nlog(n)

img

img

img


如何理解算法时间复杂度的表示法,例如 O(n²)、O(n)、O(1)、O(nlogn) 等

排序算法时间复杂度、空间复杂度、稳定性比较

时间复杂度 O(log n) 意味着什么

Copyright © tracyliu-FE 2021 all right reserved,powered by Gitbook文件修订时间: 2022-03-06 12:52:33

results matching ""

    No results matching ""