排序算法概述

排序算法是计算机科学中非常重要的基础知识，对于提高数据处理的效率至关重要。在 LeetCode 中，有很多关于排序问题的题目，以下是一些常见的排序算法及其特点。

常见排序算法

1. 冒泡排序 (Bubble Sort)

   • 时间复杂度：O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：稳定
   • 适用场景：小规模数据

2. 选择排序 (Selection Sort)

   • 时间复杂度：O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：不稳定
   • 适用场景：小规模数据

3. 插入排序 (Insertion Sort)

   • 时间复杂度：O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：稳定
   • 适用场景：小规模数据、部分有序数据

4. 快速排序 (Quick Sort)

   • 时间复杂度：O(n log n)
   • 空间复杂度：O(log n)
   • 稳定性：不稳定
   • 适用场景：大规模数据

5. 归并排序 (Merge Sort)

   • 时间复杂度：O(n log n)
   • 空间复杂度：O(n)
   • 稳定性：稳定
   • 适用场景：大规模数据

6. 堆排序 (Heap Sort)

   • 时间复杂度：O(n log n)
   • 空间复杂度：O(1)
   • 稳定性：不稳定
   • 适用场景：大规模数据

7. 希尔排序 (Shell Sort)

   • 时间复杂度：O(n^2)，但实际表现优于 O(n^2)
   • 空间复杂度：O(1)
   • 稳定性：不稳定
   • 适用场景：中等规模数据

8. 计数排序 (Counting Sort)

   • 时间复杂度：O(n + k)，其中 k 为范围
   • 空间复杂度：O(n + k)
   • 稳定性：稳定
   • 适用场景：整数排序，k 较小

9. 基数排序 (Radix Sort)

   • 时间复杂度：O(nk)，其中 k 为数字位数
   • 空间复杂度：O(nk)
   • 稳定性：稳定
   • 适用场景：整数排序，k 较小

学习资源

想要了解更多关于排序算法的知识，可以参考以下资源：

• LeetCode 排序专题

图片

冒泡排序

快速排序

归并排序