给定一个关键字序列{24,19,32,43,38,6,13,22},请写出快速排序第一趟的结果;堆排序时所建的初始堆;归并排序的全过程。然后回答上述三种排序方法中哪一种方法使用的辅助空间最少?在最坏情况下哪种方法的时间复杂度最差?
正确答案:一趟快速排序:22,19,13,6,24,38,43,32
初始大堆:43,38,32,22,24,6,13,19
二路并归:
第一趟:19,24,32,43,6,38,13,22
第二趟:19,24,32,43,6,13,22,38
第三趟:6,13,19,22,24,32,38,43
堆排序辅助空间最少,最坏情况下快速排序时间复杂度最差。
初始大堆:43,38,32,22,24,6,13,19
二路并归:
第一趟:19,24,32,43,6,38,13,22
第二趟:19,24,32,43,6,13,22,38
第三趟:6,13,19,22,24,32,38,43
堆排序辅助空间最少,最坏情况下快速排序时间复杂度最差。
答案解析:有
![](/editor/images/201705/qrcode_for_gh_573e2a458573_258.jpg)
微信扫一扫手机做题