Question

三个数据结构的问题，求高人答案

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

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

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

Answer 1

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）序列已经有序无变化，对于优化的冒泡
排序此时已经结束，对非优化的冒泡排序
还需一趟排序
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
建堆完成