2012-09-28 09:05:22
原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。http://sbp810050504.blog.51cto.com/2799422/1008930
tree[0][M]=1 5 2 6 3 7 4 排序后为:1 2 3 4 5 6 7 中位数为:4 划分后的结果为:tree[1][M]=1 2 3 4 5 6 7(这组数据有点特殊,划分后来就已经是排好序的了) (红色表示划分到中位数的左边,黑色表示划分到中位数的右边) 接着划分:tree[2][M]=1 2 3 4 5 6 7 再接着分:tree[3][M]=1 2 3 4 5 6 0 到这里已经分完了,为什么最后是0呢?在第2层(tree[2][M]),7已经分完了,所以不用再分
- void build(int level,int left,int right){
- if(left==right)return ;
- int mid=(left+right)>>1;
- int i;
- int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid]
- suppose=mid-left+1;
- for(i=left;i<=right;i++){
- if(tree[level][i]<sorted[mid]){
- suppose--;
- }
- }
- //如果suppose==1,则说明数组中值为sorted[mid]只有一个数。比如序列:1 3 4 5 6,sorted[mid]=4
- /*如果suppose>1,则说明数组中左半边值为sorted[mid]的不止一个数,为mid-suppose。比如序列:1 4 4 4 6,sorted[mid]=4
- *
- * */
- int lpos=left,rpos=mid+1;
- for(i=left;i<=right;i++){
- if(i==left){//这里是预处理,相当与初始化
- toLeft[level][i]=0;
- }else{
- toLeft[level][i]=toLeft[level][i-1];
- }
- if(tree[level][i]<sorted[mid]){//划分到中位数左边
- toLeft[level][i]++;
- tree[level+1][lpos++]=tree[level][i];
- }else if(tree[level][i]>sorted[mid]){//划分到中位数右边
- tree[level+1][rpos++]=tree[level][i];