数据结构习题请高手帮忙?10.1 一组记录的关键字序列为(64,56,23,89,10,75),写出对其进行直接插入排序

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

    建堆完成