各种排序的特点

• 时间复杂度（Time Complexity）：定性描述一个算法执行所耗费的时间，通常用大O符号表示，例如 O(n)、O(n log n)、O(n^2) 等。

• 空间复杂度（Space Complexity）：定性描述一个算法执行所需内存的大小，通常指除输入数据本身外，算法运行所需的额外内存空间。

• 稳定性（Stability）：如果排序前后，相同元素的相对位置保持不变，则称排序算法是稳定的；否则，是不稳定的。

• 内部排序（Internal Sort）：所有排序操作都在内存中完成，适用于数据量较小的情况。

• 外部排序（External Sort）：当数据量过大无法全部加载到内存时，需要使用外部存储（如磁盘）进行排序。

1. 冒泡排序 (Bubble Sort)

• 特点：
• 通过重复遍历待排序序列，比较相邻元素并交换，直到序列有序。较小的元素会像气泡一样逐渐“浮”到数列的顶端。
• 简单易懂，但效率较低，适合小规模数据排序。
• 稳定性：稳定。

• 时间复杂度：
• 平均：O(n^2)
• 最好：O(n) (当序列已经有序时，只需遍历一遍)
• 最坏：O(n^2) (当序列逆序时)

• 空间复杂度：O(1) (原地排序，只需要少量额外空间用于交换)

2. 选择排序 (Selection Sort)

• 特点：
• 每一轮从待排序的数据中找到最小（或最大）的元素，然后放到已排序序列的起始位置。
• 稳定性：不稳定。 (交换操作可能改变相同元素的相对顺序)

• 时间复杂度：
• 平均：O(n^2)
• 最好：O(n^2)
• 最坏：O(n^2)

• 空间复杂度：O(1) (原地排序，只需要少数额外变量)

3. 插入排序 (Insertion Sort)

• 特点：
• 将待排序的元素逐个插入到已排序部分的正确位置，从而构建出一个新的、有序的序列。
• 对于少量元素的排序非常有效，且对几乎有序的数据效率高。
• 稳定性：稳定。

• 时间复杂度：
• 平均：O(n^2)
• 最好：O(n) (当序列已经有序时)
• 最坏：O(n^2) (当序列逆序时)

• 空间复杂度：O(1) (原地排序，只需要一个额外空间暂存待插入元素)

4. 希尔排序 (Shell Sort)

• 特点：
• 插入排序的一种更高效的改进版本，也称递减增量排序算法。
• 通过比较距离较远的元素来加速排序，使得元素可以一次性地朝最终位置前进一大步。
• 适用于中等大小规模的数据排序。
• 稳定性：不稳定。

• 时间复杂度：
• 平均：O(n^1.3) 到 O(n^2)，具体取决于增量序列的选择。
• 最好：O(n log^2 n) 或 O(n) (取决于增量序列)
• 最坏：O(n^2) 或 O(n log^2 n)

• 空间复杂度：O(1) (原地排序)

5. 快速排序 (Quick Sort)

• 特点：
• 一种高效的排序算法，基于分治思想。
• 通过一趟排序将待排序序列分割成独立的两部分，一部分的元素都比另一部分的元素小，然后递归地对这两部分进行排序。
• 在实际应用中通常表现良好，尤其对于大规模数据集的排序。
• 稳定性：不稳定。

• 时间复杂度：
• 平均：O(n log n)
• 最好：O(n log n) (每次划分都将待排序序列分成近似相等的两部分)
• 最坏：O(n^2) (当每次选择的基准元素是最大或最小元素时，例如有序序列)

• 空间复杂度：
• 平均：O(log n) (递归调用的栈空间)
• 最坏：O(n) (当出现最坏时间复杂度时，栈深度可能达到 n)
• 可以通过优化（如三数取中、随机选择基准或尾递归优化）来避免最坏情况。

6. 归并排序 (Merge Sort)

• 特点：
• 一种经典的排序算法，核心思想是“分而治之”。
• 将待排序的数组分成两半，分别进行排序，然后再合并。这个过程递归进行，直到每个子数组只包含一个元素。
• 兼具稳定和低复杂度的特点。
• 稳定性：稳定。

• 时间复杂度：
• 平均：O(n log n)
• 最好：O(n log n)
• 最坏：O(n log n)

• 空间复杂度：O(n) (需要额外的存储空间用于合并操作)

7. 堆排序 (Heap Sort)

• 特点：
• 利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并满足堆的性质。
• 稳定性：不稳定。

• 时间复杂度：
• 平均：O(n log n)
• 最好：O(n log n)
• 最坏：O(n log n)

• 空间复杂度：O(1) (原地排序，不需要额外的存储空间)

8. 计数排序 (Counting Sort)

• 特点：
• 一种非比较型排序算法，适用于对整数或有限范围内的数据进行排序。
• 通过统计每个元素的出现次数，然后根据统计结果将元素放回正确的位置。
• 在处理整数数据时具有较好的性能，且可以突破比较排序的 O(n log n) 下界。
• 稳定性：稳定。

• 时间复杂度：
• 平均：O(n + k) (n 是元素数量，k 是数据范围大小)
• 最好：O(n + k)
• 最坏：O(n + k) (当 k 接近 n 时，复杂度接近 O(n))

• 空间复杂度：O(n + k) (需要额外的计数数组和结果数组)

9. 桶排序 (Bucket Sort)

• 特点：
• 计数排序的升级版，将数组分到有限数量的桶中，然后对每个桶中的元素进行排序，最后合并。
• 关键在于映射函数的确定，以及将数据均匀分配到桶中。
• 稳定性：稳定。

• 时间复杂度：
• 平均：O(n + k) (k 为桶数，当 k ≈ n 时为 O(n))
• 最好：O(n + k)
• 最坏：O(n^2) (当所有元素都分到同一个桶时)

• 空间复杂度：O(n + k) 或 O(n * k) (取决于桶内实现和是否存储所有桶)

10. 基数排序 (Radix Sort)

• 特点：
• 一种非比较型排序算法，适用于对整数或字符串进行排序。
• 将数据按位数进行排序，从最低位到最高位（LSD）或从最高位到最低位（MSD）。
• 稳定性：稳定。

• 时间复杂度：
• 平均：O(nk) 或 O(d(n+k)) (n 是元素个数，k 是每个数字的位数或桶大小，d 是最大位数)
• 最好：O(nk)
• 最坏：O(nk)

• 空间复杂度：O(n + k)

• 稳定性：冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序是稳定的。选择排序、希尔排序、快速排序、堆排序是不稳定的。

• 时间效率 (高到低)：
• O(n) (特定条件下的桶排序、计数排序、基数排序)
• O(n log n) (快速排序、归并排序、堆排序)
• O(n^1.3) (希尔排序在特定情况下)
• O(n^2) (冒泡排序、选择排序、插入排序)

• 空间效率 (低到高)：
• O(1) (冒泡排序、选择排序、插入排序、希尔排序、堆排序)
• O(log n) (快速排序的平均情况)
• O(n) (归并排序)
• O(n+k) 或 O(n\*k) (计数排序、桶排序、基数排序)