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

1. 冒泡排序（Bubble Sort）

• 冒泡排序是一种简单的比较排序算法，它多次遍历待排序数组，依次比较并交换相邻元素，使最大（或最小）的元素逐渐“浮”到数组的末尾。
• 时间复杂度：平均情况和最坏情况均为O(n^2)。

2. 选择排序（Selection Sort）

• 选择排序是一种简单的排序算法，它从待排序数组中选择最小的元素，然后将它与数组的第一个元素交换，接着从剩下的元素中选择次小的元素，重复这个过程。
• 时间复杂度：平均情况和最坏情况均为O(n^2)。

3. 插入排序（Insertion Sort）

• 插入排序是一种简单的排序算法，它从未排序部分取出一个元素，将其插入已排序部分的适当位置，重复这个过程。
• 时间复杂度：平均情况和最坏情况均为O(n^2)。

4. 归并排序（Merge Sort）

• 归并排序是一种分治排序算法，它将数组分成两部分，分别排序，然后将已排序的部分合并。
• 时间复杂度：平均情况和最坏情况均为O(n log n)。

5. 堆排序（Heap Sort）

• 堆排序使用堆数据结构进行排序。它首先将数组构建成最大堆或最小堆，然后将堆顶元素与堆底元素交换，重复这个过程。
• 时间复杂度：O(n log n)。

6. 计数排序（Counting Sort）

• 计数排序适用于已知输入范围的整数排序。它创建一个计数数组来存储每个元素的出现次数，然后根据计数数组构建排序后的数组。
• 时间复杂度：O(n + k)，其中 k 是输入范围。

7. 桶排序（Bucket Sort）

• 桶排序将输入数据分布到多个桶中，然后对每个桶中的数据进行排序，最后合并桶中的数据。
• 时间复杂度：平均情况为O(n + n^2/k + k)，其中 k 是桶的数量。

8. 基数排序（Radix Sort）

• 基数排序是一种非比较排序算法，它按照数字位数的顺序，从最低位到最高位进行排序。可以用于整数或字符串排序。
• 时间复杂度：O(d * (n + k))，其中 d 是数字的位数，k 是每个位数的基数。

9. 快速排序（Quick Sort）

• 快速排序是一种分治排序算法，它选择一个基准元素，将小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对左右两侧的子数组进行排序。
• 时间复杂度：
  • 平均情况时间复杂度：O(n log n)
  • 最坏情况时间复杂度：O(n^2) – 当待排序的数据已经有序或近乎有序时。
  • 最好情况时间复杂度：O(n log n) – 当待排序的数据被均匀地分割成两半。