Question

数据结构(八)排序

Answer 1

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程

算法的稳定性：对于相同关键字 使用某一排序算法后不改变其相对位置，则称该算法是稳定的

对任意n个关键字排序比较次数至少为

每次将一个待排序记录按其关键字大小插入到前面已排好的序列的子序列中，直到全部记录插入完成

算法空间复杂度为O(1)，时间复杂度为O(n ² )

先⽤折半查找找到应该插⼊的位置，再移动元素

算法时间复杂度为O(n ² )

将排序分割成若干的特殊子表，对各个子表进行直接插入排序，缩小增量d，重复上述过程，直到d=1为止

算法时间复杂度为O(n ² )

算法时间复杂度为O(n ² )

算法时间复杂度为O(n ² )，空间复杂度O(递归层数)

但平均时间复杂度O(nlog ₂ n)

选择排序：每一趟在待排元素中选取关键字最小的元素加入有序子序列

算法时间复杂度为O(n ² )

n个关键字序列 称为堆

思路：把所有⾮终端结点都检查⼀遍，是否满⾜⼤根堆的要求(根≥左、右)，如果不满⾜，则将当前结点与更⼤的⼀个孩⼦互换

时间复杂度O(nlog ₂ n)

关键字对比次数不超过4n

归并：把两个或多个已经有序的序列合并成一个

n个记录可视为n个有序子表，两两归并，直到得到长度为n的有序表

n个元素归并并排序，需要归并 躺

时间复杂度O(nlog ₂ n) ，空间复杂度为O(n)

基数排序不基于比较和移动排序，而基于关键字各位的大小进行排序

递减序列过程：

空间复杂度O(r),时间复杂度O(d(m+n))

使用归并排序，最小只需在内存中分配3块大小的缓冲区，即可对任意一个大文件进行排序

归并排序要求各个子序列有序，每次读入两个块内容进行内部排序后写回磁盘

外部排序的时间开销=读写外村时间+内部排序时间+内部归并时间

读写磁盘次数=32*3+32=128次读写，其中3为归并躺数，可以采用多路归并减小归并趟数，即减小IO次数

对于k叉树(k路归并)，若树高为h，

败者树如比赛图，可以视为一颗完全二叉树

对于k路归并使用败者树选出最小元素需要比较 次

用于内部排序的内存工作区WA可容纳l个记录，则每个初始归并段也只能包含l个记录，若文件右n个记录，则归并段数量

使用置换排序可以摆脱这个限制

归并过程中的I/O次数=归并数的WPL 2*

对于k叉归并，段数量无法构成严格k叉归并树，则需要补充n个长度为0的虚段，再进行k叉哈夫曼树的构造

初始归并段数量+虚段数量=n ₀

若

则补充(k-1)-u个虚段