Question

数据结构习题请高手帮忙?

10.1 一组记录的关键字序列为（64，56，23，89，10，75），写出对其进行直接插入排序的过程中，每一趟排序后的结果，要求从小到大进行排序。

10.2 一组记录的关键字序列为（50，38，77，26，45，69），写出对其进行冒泡排序的过程中，每一趟排序后的结果，要求从小到大进行排序。

10.3 将序列（42，33，50，18，30，29，45，12，25）调整为大顶堆。要求画出调整的全过程（不必进行堆排序）。

Answer 1

插入排序：
起始（64），（56,23,89,10,75）
第一趟 （56,64），（23,89,10,75）
第二趟 （23,56,64），（89,10,75）
第三趟 （23,56,64,89），（10,75）
第四趟 （10,23,56,64,89），（75）
第五趟 （10,23,56,64,75,89）
2. 冒泡排序
起始（50，38，77，26，45，69）
第一趟（38，50，26，45，69，77）
第二趟（38，26，45，50，69，77）
第三趟（26，38，45，50，69，77）
第四趟（26，38，45，50，69，77）
第五趟（26，38，45，50，69，77）
3. 堆排序（42，33，50，18，30，29，45，12，25）
起始：
42
33 50
18 30 29 45
12 25
自底向上建堆：
第一步调整根为18的子树：
42
33 50
25 30 29 45
12 18
第二步调整根为50的子树（已经符合大顶堆特征无需变化）
42
33 50
25 30 29 45
12 18

第三步调整根为33的子树（已经符合大顶堆特征无需变化）
42
33 50
25 30 29 45
12 18

第四步调整根为42的子树，由于移动结点时破坏了原有的平衡，需要调整两次：
第一次：
50
33 42
25 30 29 45
12 18

第二次：
50
33 45
25 30 29 42
12 18
建堆完成