优化数据结构：anyview解题——直接插入排序与改进起泡排序

在第十章的数据结构课程中，我们讨论了两个重要的排序算法的修改版本，分别是直接插入排序和冒泡排序，针对特定的数据结构——顺序表（SqList）进行优化。 首先，是关于直接插入排序的改进。原算法在10.2.1节中使用了监视哨（L.r[1..k]），这里将其调整为L.r[k+1]作为哨兵。新的`InsertSort`函数如下： ```cpp void InsertSort(SqList& L) { int i, j, k; for (i = 2; i <= L.length; i++) { L.r[0] = L.r[i]; // 将当前元素暂存到哨兵位置 int j; for (j = i - 1; j > 0 && GT(L.r[i], L.r[j]); j--) {} // 通过哨兵辅助查找插入位置 for (k = i - 1; k >= j + 1; k--) { L.r[k+1] = L.r[k]; // 逐步后移元素 } L.r[j+1] = L.r[0]; // 将哨兵位置的元素插入正确位置 } } ``` 这个改动简化了插入过程，通过哨兵单元快速找到插入位置，提高了排序效率。 其次，是冒泡排序的优化。原始算法使用布尔变量`change`表示是否发生过交换，这里将其改为整型变量`change`，记录最后一次交换的位置。`BubbleSort`函数如下： ```cpp void BubbleSort(SqList& L) { int i, j, change = 1; for (i = L.length; i > 1; i = change) { // 当一轮没有发生交换时，设置下一轮的起始位置 for (change = 1, j = 1; j < i; j++) { if (GT(L.r[j], L.r[j+1])) { Swap(L.r[j], L.r[j+1]); // 交换元素 change = j + 1; // 更新交换位置 } } } } ``` 这种改变使得算法更加直观，便于理解和执行，同时保持了排序的逻辑。 这两个算法的共同点是都利用了顺序表（SqList）的特点，通过哨兵和辅助变量来提高排序的效率。它们在课程设计题中作为练习，旨在让学生理解并熟练掌握不同数据结构下的排序算法优化策略。学习这些内容有助于提高编程实践能力和对排序算法的理解深度。