排序趟数问题

1. 冒泡排序

• 趟数：最多 n-1 趟（n为元素个数）
• 每趟操作：比较相邻元素，将最大元素“冒泡”到末尾。
• 优化：若某趟无交换，可提前终止（如数组已有序时仅需1趟）。
• 示例：
  • 数组 [5,3,1,2,4] 需要4趟完成排序。

---

2. 选择排序

• 趟数：固定 n-1 趟
• 每趟操作：每趟选择未排序部分的最小元素，与当前趟首位交换。
• 特点：无论数据是否有序，均需完整执行所有趟。
• 示例：
  • 数组 [5,3,1,2,4] 固定需要4趟。

---

3. 插入排序

• 趟数：n-1 趟
• 每趟操作：每趟将当前元素插入已排序部分的正确位置。
• 优化：若数据基本有序，每趟插入操作时间接近O(1)。
• 示例：
  • 数组 [1,2,3,5,4] 需要4趟，最后一趟将4插入正确位置。

---

4. 快速排序

• 趟数：平均递归深度为 log n 层（非严格“趟数”）
• 每趟操作：每层递归进行一次分区（Partition），将数组分为左右子区间。
• 特点：
  • 实际趟数与分区的平衡性相关（如最坏情况单趟分割为 O(n) 层）。
• 示例：
  • 数组 [3,1,2,5,4] 平均需要约 log 5 ≈ 3 层递归完成排序。

---

5. 归并排序

• 趟数：log n 趟合并（每趟合并相邻子数组）
• 每趟操作：自底向上逐层合并子数组（如长度为1→2→4→8…）。
• 示例：
  • 数组 [5,3,1,2,4] 需要3趟合并（合并至长度8时结束）。

---

6. 堆排序

• 趟数：n-1 趟交换+调整
• 每趟操作：
  1. 建堆后，每次将堆顶元素（最大值）与末尾交换（1趟交换）；
  2. 调整剩余堆（每趟调整复杂度为O(log n)）。
• 示例：
  • 数组 [5,3,1,2,4] 需要4趟交换完成排序。

---

7. 基数排序（LSD）

• 趟数：等于数据最大位数 d
• 每趟操作：按某一位分配到桶中，再按桶顺序收集数据。
• 示例：
  • 排序 [170, 45, 75, 90, 802]，最大位数3，需3趟（个位→十位→百位）。

---

8. 希尔排序

• 趟数：取决于增量序列（如 gap = n/2, n/4, ..., 1）
• 每趟操作：每趟按不同间隔进行插入排序。
• 示例：
  • 数组 [5,3,1,2,4] 使用增量序列 [2,1]，需2趟。

---

总结

算法	趟数定义	是否与数据相关
冒泡排序	最多 n-1 趟	是（可提前终止）
插入排序	n-1 趟	是（数据有序时高效）
归并排序	log n 趟合并	否（固定分治策略）
基数排序	d 趟（d为位数）	否
快速排序	平均 log n 层递归	是（依赖分区平衡性）

---

注意事项

1. 趟数 ≠ 时间复杂度：例如插入排序每趟操作复杂度为O(n)，但总时间复杂度仍为O(n²)。
2. 实际应用：优先关注时间复杂度、空间复杂度及稳定性，而非单纯趟数。
3. 优化算法：如Timsort会根据数据特征动态调整策略，趟数不固定。