本文共 481 字,大约阅读时间需要 1 分钟。
归并排序
归并排序是采用分治的思想,将数组划分为两个子数组,然后递归的将每个子数组再进行划分,直到数组中只剩一下一个元素,然后开始排序合并,直到将所有的子数组合并完成,整个数据就是有序的了。
归并排序一个重要的操作函数就是合并函数
时间复杂度:将数组分成的子数组 用二叉树表示,假设共有n层,第k层共有2的K次方个子数组,每个子数组的长度是2的n-k次方 所以每一层的比较次数是2的n次方,n层就是n*2的n次方次比较,n=logN 所以 时间复杂度就是NlgN
空间复杂度 N 因为有一个临时数组
外部排序
假设文件需要分成k块读入,需要从小到大进行排序。
(1)依次读入每个文件块,在内存中对当前文件块进行排序(应用恰当的内排序)。此时,每块文件相当于一个由小到大排列的有序队列。
(2)在内存中建立一个最小值堆,读入每块文件的队列头。
(3)弹出堆顶元素,如果元素来自第i块,则从第i块文件中补充一个元素到最小值堆。弹出的元素暂存至临时数组。
(4)当临时数组存满时,将数组写至磁盘,并清空数组内容。
(5)重复过程(3)、(4),直至所有文件块读取完毕。
转载地址:http://hpgsi.baihongyu.com/