常见的排序算法及时间复杂度

  1. 冒泡排序(Bubble Sort)
  • 冒泡排序是一种简单的比较排序算法,它多次遍历待排序数组,依次比较并交换相邻元素,使最大(或最小)的元素逐渐“浮”到数组的末尾。
  • 时间复杂度:平均情况和最坏情况均为O(n^2)。
  1. 选择排序(Selection Sort)
  • 选择排序是一种简单的排序算法,它从待排序数组中选择最小的元素,然后将它与数组的第一个元素交换,接着从剩下的元素中选择次小的元素,重复这个过程。
  • 时间复杂度:平均情况和最坏情况均为O(n^2)。
  1. 插入排序(Insertion Sort)
  • 插入排序是一种简单的排序算法,它从未排序部分取出一个元素,将其插入已排序部分的适当位置,重复这个过程。
  • 时间复杂度:平均情况和最坏情况均为O(n^2)。
  1. 归并排序(Merge Sort)
  • 归并排序是一种分治排序算法,它将数组分成两部分,分别排序,然后将已排序的部分合并。
  • 时间复杂度:平均情况和最坏情况均为O(n log n)。
  1. 堆排序(Heap Sort)
  • 堆排序使用堆数据结构进行排序。它首先将数组构建成最大堆或最小堆,然后将堆顶元素与堆底元素交换,重复这个过程。
  • 时间复杂度:O(n log n)。
  1. 计数排序(Counting Sort)
  • 计数排序适用于已知输入范围的整数排序。它创建一个计数数组来存储每个元素的出现次数,然后根据计数数组构建排序后的数组。
  • 时间复杂度:O(n + k),其中 k 是输入范围。
  1. 桶排序(Bucket Sort)
  • 桶排序将输入数据分布到多个桶中,然后对每个桶中的数据进行排序,最后合并桶中的数据。
  • 时间复杂度:平均情况为O(n + n^2/k + k),其中 k 是桶的数量。
  1. 基数排序(Radix Sort)
  • 基数排序是一种非比较排序算法,它按照数字位数的顺序,从最低位到最高位进行排序。可以用于整数或字符串排序。
  • 时间复杂度:O(d * (n + k)),其中 d 是数字的位数,k 是每个位数的基数。
  1. 快速排序(Quick Sort)
  • 快速排序是一种分治排序算法,它选择一个基准元素,将小于基准的元素放在左边,大于基准的元素放在右边,然后递归地对左右两侧的子数组进行排序。
  • 时间复杂度:
    • 平均情况时间复杂度:O(n log n)
    • 最坏情况时间复杂度:O(n^2) – 当待排序的数据已经有序或近乎有序时。
    • 最好情况时间复杂度:O(n log n) – 当待排序的数据被均匀地分割成两半。
图片[1]-常见的排序算法及时间复杂度-不念博客
© 版权声明
THE END
喜欢就支持一下吧
点赞65赞赏 分享
评论 抢沙发
头像
欢迎光临不念博客,留下您的想法和建议,祝您有愉快的一天~
提交
头像

昵称

取消
昵称代码图片

    暂无评论内容