数据结构考研分类复习真题 第十章 答案[15]

快速排序

() 在最好情况下假设每次划分能得到两个长度相等的子文件文件的长度n=k那么第一遍划分得到两个长度均为ën/û的子文件第二遍划分得到个长度均为ën/û的子文件以此类推总共进行k=log(n+)遍划分各子文件的长度均为排序完毕当n=时k=在最好情况下第一遍需比较次第二遍分别对两个子文件(长度均为k=)进行排序各需次共次即可

() 在最好情况下快速排序的原始序列实例

() 在最坏情况下若每次用来划分的记录的关键字具有最大值(或最小值)那么只能得到左(或右)子文件其长度比原长度少因此若原文件中的记录按关键字递减次序排列而要求排序后按递增次序排列时快速排序的效率与冒泡排序相同其时间复杂度为O(n)所以当n=时最坏情况下的比较次数为次

() 在最坏情况下快速排序的初始序列实例 要求按递增排序

该排序方法为快速排序

不是因为当序列已有序时快速排序将退化成冒泡排序时间复杂度为O(n)当待排序序列无序使每次划分完成后枢轴两侧子文件长度相当此时快速排序性能最好

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []