排序算法总述

排序算法是是一些列很基础的算法的集合,它们有着共同的特点。就是为事物进行排序。本系列的文章是对这些算法进行一个总结,本系列涉及到的算法如下。

  • 冒泡排序
  • 快速排序
  • 插入排序
  • 希尔排序
  • 选择排序
  • 堆排序
  • 归并排序
  • 基数排序
  • 桶排序
  • 计数排序

算法时间和复杂度总结

上述算法的特点可以总结如下:

算法名称 时间复杂度(平均) 时间复杂度(最坏) 时间复杂度(最好) 空间复杂度 稳定性
插入排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定
希尔排序 $O(n^{1.3})$ $O(n^2)$ $O(n)$ $O(1)$ 不稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(1)$ 不稳定
冒泡排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定
快速排序 $O(nlog_2n)$ $O(n^2)$ $O(nlog_2n)$ $O(nlog_2n)$ 不稳定
归并排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(n)$ 稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(n+k)$ 稳定
桶排序 $O(n+k)$ $O(n^2)$ $O(n)$ $O(n+k)$ 稳定
基数排序 $O(n*k)$ $O(n*k)$ $O(n*k)$ $O(n+k)$ 稳定

微信公众号

© 2018 ray