广东工大数据结构AnyView作业：改进排序算法（直接插入与冒泡）

在广东工业大学的数据结构课程中，针对anyview作业系统的第十章，我们探讨了两个关键的算法实现：直接插入排序和起泡排序。这些题目旨在帮助学生理解和应用数据结构中的基本操作。 1. **直接插入排序的改进版本** (10.23②) 教材原版的直接插入排序算法通过逐个元素比较和交换来对有序链表`L`进行排序。这里引入了一个新的改动，即使用`L.r[k+1]`作为监视哨，这是一种优化策略。在新版本的`InsertSort`函数中，首先从倒数第二个元素开始遍历，将当前元素与后一个元素比较，如果当前元素大于后一个元素，则交换它们的位置。同时，将较大的元素移动到哨兵位置`L.r[L.length+1]`。然后，继续检查剩余元素，直到找到第一个大于`L.r[L.length+1]`的元素，将该元素前移，确保已排序部分的稳定性。这种方法减少了不必要的元素移动，提高了效率。 2. **起泡排序的优化（10.26②）** 原有的起泡排序算法使用布尔变量`change`表示是否进行了交换，以此决定是否结束一次排序循环。在这里，改为了使用一个整型变量`lastExchange`来记录最后一次交换发生的位置，这样可以避免冗余的判断条件。在`BubbleSort`函数中，每次循环会更新`lastExchange`，并在下一次循环开始时将其作为终止条件。这样，当遍历到`lastExchange`位置的元素未发生交换时，就表明序列已经有序，可以直接结束循环。这不仅简化了代码，还提高了算法的执行效率。 这两个题目要求学生理解并实践数据结构中的排序算法，特别是对于直接插入排序和起泡排序这两种基础排序方法，它们在实际编程中的优化策略对于提高程序性能至关重要。同时，通过实现这些函数，学生需要熟练掌握顺序表的定义和使用，以及如何调用自定义的比较和交换函数来完成排序过程。理解这些概念有助于深入理解算法的原理和优化手段，是数据结构学习的重要环节。