對于復(fù)制代價很高的元素，通過某種排序算法進(jìn)行間接排序。
排序完成后，再一次復(fù)制回去。
這樣需要一個中間數(shù)組，進(jìn)行2N次復(fù)制。
通過原地置換，我們可以只使用一個中間變量，最多進(jìn)行3N/2次復(fù)制即可達(dá)到目的。
如index[1]==3。那么，說明array[1]這個位置應(yīng)該放的是array[3].我們將array[1]保存到tmp中。
然后array[1]=array[3].現(xiàn)在array[3]是可以放置的了。那么我們看array[3]應(yīng)該放什么，如果index[3]==2,剛好我們把tmp放回去。
不然，我們繼續(xù)按這個鏈找下去。
如果鏈長為x.那么我們需要x+1次復(fù)制。
鏈長最小為2.所以我們最多只需要3N/2次復(fù)制即可。
int?indirect_sort(int?*array,int?len)?{
????if(array==NULL||len<=0)?return?0;
????
????//索引數(shù)組
????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]已經(jīng)放到了最終的地方。
????????if(?index[i]?==?i)
????????????continue;
????????else{
????????????tmp?=?array[i];
????????????j?=?i;
????????????while(?index[j]!=i?){
????????????????//array[j]應(yīng)該放的是array[index[j]]
????????????????array[j]?=?array[index[j]];
????????????????tmp2?=?j;
????????????????j?=?index[j];
????????????????//原來的array[j]已經(jīng)放好了
????????????????index[tmp2]?=?tmp2;
????????????}
????????????array[j]?=?tmp;
????????????index[j]?=?j;
????????}
????}
????return?1;
}