[基础算法复习]原地置换的间接排序

对于复制代价很高的元素,通过某种排序算法进行间接排序。
排序完成后,再一次复制回去。
这样需要一个中间数组,进行2N次复制。
通过原地置换,我们可以只使用一个中间变量,最多进行3N/2次复制即可达到目的。

如index[1]==3。那么,说明array[1]这个位置应该放的是array[3].我们将array[1]保存到tmp中。
然后array[1]=array[3].现在array[3]是可以放置的了。那么我们看array[3]应该放什么,如果index[3]==2,刚好我们把tmp放回去。
不然,我们继续按这个链找下去。
如果链长为x.那么我们需要x+1次复制。
链长最小为2.所以我们最多只需要3N/2次复制即可。

int indirect_sort(int *array,int len) {

    
if(array==NULL||len<=0return 0;
    
    
//索引数组
    int *index = malloc(sizeof(int)*(len));
    
if(index==NULL) return 0;

    
int i,j,largest,tmp,tmp2;

    
for(i=0;i<len;++i){
        index[i] 
= i;
    }

    
//插入排序
    for(i=1;i<len;++i){
        tmp 
= index[i];
        
for(j=i;j-1>=0&&array[index[j-1]]>array[tmp];--j){
            index[j] 
= index[j-1];
        }
        index[j] 
= tmp;
    }

    
for(i=0;i<len;++i){
        
//如果index[i]==i,说明array[i]已经放到了最终的地方。
        if( index[i] == i)
            
continue;
        
else{
            tmp 
= array[i];
            j 
= i;
            
while( index[j]!=i ){
                
//array[j]应该放的是array[index[j]]
                array[j] = array[index[j]];
                tmp2 
= j;
                j 
= index[j];
                
//原来的array[j]已经放好了
                index[tmp2] = tmp2;
            }
            array[j] 
= tmp;
            index[j] 
= j;
        }
    }

    
return 1;
}


posted on 2009-07-16 11:52 YZY 阅读(1047) 评论(0)  编辑 收藏 引用 所属分类: Algorithm基础算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜