基于二次取中的选择算法
2016-01-01 13:13:28 0 举报
二次取中选择算法是一种基于排序的选择算法,其基本思想是每次从未排序的子序列中选取中间的元素作为基准元素,然后将小于基准元素的值放在左侧,大于基准元素的值放在右侧。接着,对左右两个子序列分别递归地进行同样的操作,直到子序列的长度为1或0。最后,将各个子序列中的基准元素按照顺序拼接起来,就得到了最终的有序序列。该算法的时间复杂度为O(nlogn),适用于大规模数据的排序和查找。
作者其他创作
大纲/内容
定义区间长度n=high-low+1
结束
对数组elems中的low到high区间元素找到v的位置j
jlow+k-1?
j=low+k-1?
递归调用本算法找数组elems从j+1到high中的第k-(j-low+1)小的元素
再递归调用本算法找到M数组中的中位数v
对groups个分组中的每一个分组递归调用本算法找到中位数存放在M中
递归调用本算法找数组elems从low到j中的第k小的元素
是
否
n≤r?
返回第k小元素elems[low+k]
返回elems[j]
定义分组数groups=n/r数组M存放groups个组的中间值
利用插入排序InsertionSort对elems中的low到high的元素进行排序
开始
0 条评论
下一页