常见排序算法的复杂度

常见的排序算法包括冒泡排序（Bubble Sort）、选择排序（Selection Sort）、插入排序（Insertion Sort）、希尔排序（Shell Sort）、归并排序（Merge Sort）、快速排序（Quick Sort）、堆排序（Heap Sort）和计数排序（Counting Sort）、桶排序（Bucket Sort）、基数排序（Radix Sort）等。下面列出了这些排序算法的时间复杂度和空间复杂度（平均/最好/最坏情况）：

1. 冒泡排序（Bubble Sort）

• 时间复杂度：
  • 平均/最坏情况：O(n^2)
  • 最好情况：O(n)（当输入序列已经是排序好的）
• 空间复杂度：O(1)（原地排序）

2. 选择排序（Selection Sort）

• 时间复杂度：
  • 平均/最好/最坏情况：O(n^2)
• 空间复杂度：O(1)（原地排序）

3. 插入排序（Insertion Sort）

• 时间复杂度：
  • 平均/最好情况：O(n^2)
  • 最坏情况：O(n^2)
  • 对于部分已排序的数据集，时间复杂度可以优化到O(n)
• 空间复杂度：O(1)（原地排序）

4. 希尔排序（Shell Sort）

• 时间复杂度：
  • 平均情况：依赖于增量序列，难以准确计算，但通常比O(n^2)好
  • 最好情况：O(nlogn)
  • 最坏情况：O(n^s)对于某个s > 1，取决于增量序列
• 空间复杂度：O(1)（原地排序）

5. 归并排序（Merge Sort）

• 时间复杂度：
  • 平均/最好/最坏情况：O(nlogn)
• 空间复杂度：O(n)（需要额外的存储空间用于合并）

6. 快速排序（Quick Sort）

• 时间复杂度：
  • 平均情况：O(nlogn)
  • 最好情况：O(nlogn)
  • 最坏情况：O(n^2)（当分区总是发生在最小或最大元素时）
• 空间复杂度：
  • 平均情况：O(logn)（递归栈空间）
  • 最坏情况：O(n)（递归栈空间）

7. 堆排序（Heap Sort）

• 时间复杂度：
  • 平均/最好/最坏情况：O(nlogn)
• 空间复杂度：O(1)（原地排序，除了几个临时变量外）

8. 计数排序（Counting Sort）

• 时间复杂度：O(n+k)（k是输入的最大值）
• 空间复杂度：O(k)

9. 桶排序（Bucket Sort）

• 时间复杂度：
  • 平均情况：O(n+k)（k是桶的数量）
  • 最坏情况：O(n^2)（如果桶内的排序非常低效）
• 空间复杂度：O(n+k)

10. 基数排序（Radix Sort）

• 时间复杂度：O(d*(n+k))，其中d是位数，k是基数
• 空间复杂度：O(n+k)

这些排序算法各有优缺点，适用于不同的数据场景和需求。在实际应用中，需要根据具体情况选择合适的排序算法。