严蔚敏《数据结构》：内部排序详解与直接插入法

数据结构是计算机科学中的基础概念，涉及到数据的组织、存储和操作方式。《数据结构（C语言版）》由严蔚敏和吴伟明编著，是清华大学计算机系列教材之一，旨在帮助读者理解数据结构的核心原理和常见算法。 内部排序是数据结构中的一个重要子领域，它关注的是将一组存储在内存中的记录按照特定的排序码（如关键字）进行有序排列的过程。根据排序码值是否发生相对位置变化，内部排序可分为稳定排序和不稳定排序。稳定排序如插入排序，确保相同排序码的记录保持原有的相对顺序；而不稳定排序如快速排序，可能会改变这些记录的相对位置。 内部排序方法众多，这里重点介绍几种常见的插入排序变种： 1. **直接插入排序**：基本思想是从第二个记录开始，依次在已排序部分找到合适的位置插入，直到所有记录排序完毕。如对给定的整数序列 {49, 38, 65, 97, 76, 13, 27, 49} 进行排序，直接插入排序通过不断移动记录实现了从无序到有序的过程。 2. **折半插入排序**：这是一种改进的插入排序，通过二分查找来确定插入位置，提高了效率。 3. **希尔排序**：采用间隔序列的插入排序，通过缩小间隔逐步接近直接插入排序，加速了排序速度。 **交换排序**又包括 **起泡排序**，每次比较相邻元素并交换位置，直到整个序列有序。另一个例子是 **快速排序**，利用分治策略，通过选取基准值将数组分为两部分，对每一部分递归地进行排序，具有较高的平均时间复杂度。 4. **选择排序**：简单选择排序每次从未排序的部分选出最小（或最大）的记录放到已排序部分的末尾，过程直观但效率较低。 在这个章节中，作者还假设使用顺序表（SqList）作为数据结构，用以存储整数类型的记录。顺序表定义了关键字项和其它数据项，以及用于表示列表状态的数据结构，如记录数量（length）和一个作为哨兵的0单元。直接插入排序的具体实现展示了如何遍历列表，通过比较和交换操作完成排序。 这个课件内容涵盖了内部排序的基本概念、分类、典型算法以及其实现细节，为学习者提供了实用的编程技能和理论指导，有助于深入理解和掌握数据结构在C语言环境下的应用。