以下是C++中常见排序算法的详细对比，包括时间复杂度、空间复杂度、稳定性、基本概念及主要区别：

1. 冒泡排序（Bubble Sort）

• 概念：通过重复遍历数组，每次比较相邻元素并交换位置，使较大元素"冒泡"到数组末端。
• 时间复杂度：
  • 最佳：O(n)（已排序数组，加入优化标志）
  • 平均：O(n²)
  • 最坏：O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定性：稳定（相等元素不交换位置）
• 特点：简单直观，适合小规模数据，但效率低。

2. 选择排序（Selection Sort）

• 概念：每次从剩余元素中找到最小（大）值，放到已排序部分的末尾。
• 时间复杂度：
  • 最佳/平均/最坏：O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定（可能交换相等元素的相对位置）
• 特点：实现简单，但无论数据分布如何，效率固定为O(n²)。

3. 插入排序（Insertion Sort）

• 概念：将元素逐个插入到已排序部分的适当位置，类似整理扑克牌。
• 时间复杂度：
  • 最佳：O(n)（已排序数组）
  • 平均：O(n²)
  • 最坏：O(n²)
• 空间复杂度：O(1)（原地排序）
• 稳定性：稳定
• 特点：适合小规模或基本有序的数据，实际应用中效率高于冒泡和选择排序。

4. 希尔排序（Shell Sort）

• 概念：插入排序的改进版，通过分组（按步长）进行插入排序，逐步缩小步长至1。
• 时间复杂度：
  • 取决于步长序列，平均约为O(n¹.³)
  • 最坏：O(n²)（简单步长）或O(n log²n)（Hibbard步长）
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定
• 特点：突破O(n²)瓶颈，适合中等规模数据。

5. 归并排序（Merge Sort）

• 概念：分治法思想，将数组递归分为两半，排序后合并两个有序子数组。
• 时间复杂度：
  • 最佳/平均/最坏：O(n log n)
• 空间复杂度：O(n)（需要额外数组存储合并结果）
• 稳定性：稳定
• 特点：效率高且稳定，适合大规模数据，但需要额外空间。

6. 快速排序（Quick Sort）

• 概念：分治法思想，选择基准元素，将数组分为小于和大于基准的两部分，递归排序。
• 时间复杂度：
  • 最佳/平均：O(n log n)
  • 最坏：O(n²)（已排序数组且选两端为基准）
• 空间复杂度：O(log n)~O(n)（递归栈空间）
• 稳定性：不稳定
• 特点：实际应用中最快的排序算法之一，适合大规模数据，对缓存友好。

7. 堆排序（Heap Sort）

• 概念：利用堆数据结构，先构建最大（小）堆，反复提取堆顶元素并调整堆。
• 时间复杂度：
  • 最佳/平均/最坏：O(n log n)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定
• 特点：效率稳定，无需额外空间，但缓存性能较差。

8. 计数排序（Counting Sort）

• 概念：非比较排序，通过统计元素出现次数，直接计算元素在结果中的位置。
• 时间复杂度：
  • 最佳/平均/最坏：O(n + k)（k为数据范围）
• 空间复杂度：O(n + k)
• 稳定性：稳定
• 特点：适合数据范围小且为整数的场景（如年龄、成绩）。

9. 桶排序（Bucket Sort）

• 概念：将数据分到有限数量的桶中，对每个桶单独排序（通常用插入排序），最后合并。
• 时间复杂度：
  • 最佳/平均：O(n + k)
  • 最坏：O(n²)（所有元素放入同一桶）
• 空间复杂度：O(n + k)
• 稳定性：稳定
• 特点：适合均匀分布的数据，桶的设计影响效率。

10. 基数排序（Radix Sort）

• 概念：非比较排序，按位数从低到高（或高到低）依次排序，依赖计数排序等稳定排序。
• 时间复杂度：
  • 最佳/平均/最坏：O(d*(n + k))（d为位数，k为基数）
• 空间复杂度：O(n + k)
• 稳定性：稳定
• 特点：适合整数或可转换为固定位数的类型（如字符串）。

算法选择建议：

• 小规模数据：插入排序、冒泡排序
• 中等规模数据：希尔排序
• 大规模数据：快速排序、归并排序、堆排序
• 数据范围小：计数排序、桶排序
• 稳定性要求高：归并排序、冒泡排序、插入排序、计数排序

实际开发中，C++标准库的std::sort通常采用 introsort（快速排序、堆排序、插入排序的混合），在不同场景下自动切换最优算法。