根据您提供的课件内容（《第三十章 内部排序》），其中详细介绍了多种内部排序方法。

课件将这些排序方法按基本思想（策略）主要分为五大类。以下是整理好的所有排序方法及其分类：

1. 插入排序 (Insertion Sort)

基本思想：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序的子序列的适当位置，直到所有记录都插入为止 1。

  • 直接插入排序 (Direct Insertion Sort) 2

    • 最基本的插入排序方法。

  • 希尔排序 (Shell Sort) 3

    • 又称“缩小增量”排序，是对直接插入排序的改进。

  • 其他插入排序：

    • 折半插入排序 (Binary Insertion Sort) 4：利用折半查找来寻找插入位置。

    • 2-路插入排序 5：旨在减少移动记录的次数，需要辅助空间。

    • 表插入排序 6：采用链表存储结构，在排序过程中不移动记录，只改变指针。

2. 交换排序 (Exchange Sort)

基本思想：两两比较待排序记录的关键字，如果发生逆序则交换，直到整个序列中没有反序的记录为止 7。

  • 冒泡排序 (Bubble Sort) 8

    • 通过相邻记录的交换，让较大的记录像气泡一样“浮”到序列末端。

  • 快速排序 (Quick Sort) 9

    • 被认为是平均性能最好的内部排序方法 10。通过枢轴（pivot）将序列划分为两部分，递归进行排序。

3. 选择排序 (Selection Sort)

基本思想：不断地从待排序的记录序列中选取关键字最小的记录，放在已排好序的序列的最后 11。

  • 简单选择排序 (Simple Selection Sort) 12

    • 通过比较找出最小关键字。

  • 树形选择排序 (Tree Selection Sort) 13

    • 也称锦标赛排序，借助“淘汰赛”的思想，使用完全二叉树来辅助选择。

  • 堆排序 (Heap Sort) 14

    • 利用“堆”这种数据结构（大顶堆或小顶堆）来进行排序，是对树形选择排序的改进，空间效率更高。

4. 归并排序 (Merge Sort)

基本思想：利用“归并”技术，将两个或两个以上的有序子序列合并成一个新的有序序列 15。

  • 二路归并排序 16

    • 最常见的归并排序形式，将序列两两合并。

5. 基数排序 (Radix Sort)

基本思想：不需要进行关键字的比较，而是借助“多关键字排序”的思想，按关键字的“位”（如个位、十位）进行“分配”和“收集” 17171717。

  • 多关键字排序 18

  • 链式基数排序 19

附：各种内部排序方法的性能比较

课件最后提供了一个总结表，对比了主要排序方法的性能 20：

方法 平均时间 最坏所需时间 附加空间 稳定性
直接插入排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 $O(n^{1.3})$ — $O(1)$ 不稳定
直接选择排序 $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(n \log_2 n)$ $O(n \log_2 n)$ $O(1)$ 不稳定
冒泡排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n \log_2 n)$ $O(n^2)$ $O(\log_2 n)$ 不稳定
归并排序 $O(n \log_2 n)$ $O(n \log_2 n)$ $O(n)$ 稳定
基数排序 $O(d(n+r))$ $O(d(n+r))$ $O(n+r)$ 稳定