06. 排序

排序

1. 基本概念

• 排序：将一组数据元素按关键字递增或递减排列
• 稳定性：相等元素排序前后相对位置不变
• 时间复杂度、空间复杂度

2. 插入排序

• 直接插入排序：依次插入，O(n^2)
• 折半插入排序：用二分法查找插入位置，O(n^2)

3. 冒泡排序

• 相邻元素两两比较，O(n^2)，稳定

4. 选择排序

• 每次选最小（大）元素放到前面，O(n^2)，不稳定

5. 希尔排序

• 分组插入排序，增量递减，O(n^1.3~n^2)

6. 快速排序

• 分治法，选基准，左右分区递归，O(n log n)~O(n^2)，不稳定

7. 堆排序

• 构建大（小）顶堆，反复取堆顶，O(n log n)，不稳定

8. 归并排序

• 分治法，递归分组，合并有序，O(n log n)，稳定

9. 基数排序

• 按位分组，低位优先，O(dn)，稳定

10. 外部排序

• 适合大数据量，常用多路归并

11. 各种排序算法比较与应用

• 比较时间、空间、稳定性、适用场景

练习题

1. 简述直接插入排序和冒泡排序的基本思想。
2. 快速排序的基本步骤是什么？
3. 归并排序和堆排序的时间复杂度是多少？
4. 哪些排序算法是稳定的？
5. 外部排序适合什么场景？