原地置换的间接排序 派出所, 游戏机, 元素

yuyang911220

对于复制代价很高的元素，通过某种排序算法进行间接排序。
排序完成后，再一次复制回去。
这样需要一个中间数组，进行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<=0) return
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;
    }

    //插入排序

for(i=1;i<len;++i){
        tmp = index;
        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，说明array已经放到了最终的地方。

if( index == i)
            continue;
        else{
            tmp = array;
            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;
}

yuchengze

支持帮顶，路过支持一下