這題出自2013年谷歌的校招筆試。題目是這樣的:

長度為N的數(shù)組亂序放著0至N-1,現(xiàn)在只能進(jìn)行0與其他元素的swap,請?jiān)O(shè)計(jì)并實(shí)現(xiàn)排序。

讀完題目，立馬就有了一個(gè)簡單的思路。既然是0至N-1存放在這個(gè)數(shù)組中，那么排序后的數(shù)組是0 1 2 3 .... ,也就是每個(gè)元素的值和它的下標(biāo)是一致的。這給了我們一個(gè)投機(jī)取巧的機(jī)會(huì)。每個(gè)元素歸為可以分為兩步來歸位。對于位置X，第一步 將此處的值 和 0進(jìn)行交換。 第二步 將此處的值(此時(shí)為0) 和 值X進(jìn)行交換。順著這么一個(gè)簡單的思路，我們可以先寫出如下蠢爆了的代碼(你可以直接跳過這段代碼進(jìn)行閱讀，畢竟這種low代碼沒啥可讀的，我寫下只是為了記錄自己思考的整個(gè)過程，寫這種Low代碼的好處大約是，這種代碼low到不假思索，可以邊寫邊思考，寫的同時(shí)就可以考慮更優(yōu)的方案了。而此代碼稍加改進(jìn)可能就會(huì)成為更優(yōu)的方案，也不算浪費(fèi)體力吧)

inline void swap(int *_arr,int _index1,int _index2)
{
    _arr[_index1] = (_arr[_index1] ^ _arr[_index2]);
    _arr[_index2] = (_arr[_index1] ^ _arr[_index2]);
    _arr[_index1] = (_arr[_index1] ^ _arr[_index2]);
}

int find(int *_arr,int _num)
{
    int ix = 0;
    while(_arr[ix] != _num)
        ix++;
    return ix;
}

void swap_sort(int *_arr,int _len)
{
    for(int ix=0;ix<_len;ix++)
    {
        int zero_index = find(_arr ,0);
        swap(_arr,ix,zero_index);
        int ix_index   = find(_arr ,ix);
        swap(_arr,ix,ix_index);
    }
}

這樣一份代碼也就初步將我們的想法實(shí)現(xiàn)了，其實(shí)不用寫完，寫一半時(shí) '寫出高效代碼' 的覺悟就讓我們敲不下去鍵盤了。這樣的代碼效率低到令人發(fā)指，最主要就是find這個(gè)函數(shù)似乎是沒有必要的，我們要去記住每個(gè)元素的位置，而不是每次都要去尋找。于是我們在 swap_sort函數(shù)的開頭添加如下三行代碼

int *index_arr = new int[_len];
for(int ix=0;ix<_len;ix++)
  index_arr[_arr[ix]] = ix;

index_arr數(shù)組就是記錄了每個(gè)數(shù)在_arr數(shù)組中所處的位置。
這樣我們就不必每次找尋了。代碼變成了下面的樣子

  int *index_arr = new int[_len];
    for(int ix=0;ix<_len;ix++)
        index_arr[_arr[ix]] = ix;
    for(int ix=0;ix<_len;ix++)
    {
        swap(_arr,ix,index_arr[0]);
        swap(_arr,ix,index_arr[ix]);
    }

感覺哪里不對，我們不能犯了刻舟求劍的錯(cuò)誤 水是流動(dòng)的 我們的數(shù)組也是在變動(dòng)的，自然記錄元素位置的數(shù)組也要跟著變動(dòng)。繼續(xù)添加兩行

int *index_arr = new int[_len];
    for(int ix=0;ix<_len;ix++)
        index_arr[_arr[ix]] = ix;
    for(int ix=0;ix<_len;ix++)
    {
        swap(_arr,ix,index_arr[0]);
        swap(index_arr,0,_arr[index_arr[0]]);

        swap(_arr,ix,index_arr[ix]);
        swap(index_arr,0,ix);
    }

這里需要注意 swap(index_arr,0,_arr[index_arr[0]]); 這句代碼是我們交換了原數(shù)組中0和位于ix處值的位置(記為val_ix)，那么我們自然要在記錄位置的數(shù)組中反映。記錄位置數(shù)組的變化是這樣的：位置0記錄了原數(shù)組中0所處的位置。位置val_ix記錄了val_ix在原數(shù)組中的位置。我們也交換它們的內(nèi)容。swap(index_arr,0,val_ix)即可?？墒莢al_ix的值已經(jīng)被我們交換了位置，所以我們要去它新的位置找它，也就是0原來所處的位置。
完整代碼如下:

inline void swap(int *_arr,int _index1,int _index2)
{
    _arr[_index1] = (_arr[_index1] ^ _arr[_index2]);
    _arr[_index2] = (_arr[_index1] ^ _arr[_index2]);
    _arr[_index1] = (_arr[_index1] ^ _arr[_index2]);
}



void swap_sort(int *_arr,int _len)
{
    int *index_arr = new int[_len];
    for(int ix=0;ix<_len;ix++)
        index_arr[_arr[ix]] = ix;
    for(int ix=0;ix<_len;ix++)
    {
        swap(_arr,ix,index_arr[0]);
        swap(index_arr,0,_arr[index_arr[0]]);

        swap(_arr,ix,index_arr[ix]);
        swap(index_arr,0,ix);
    }
}
int main(int argc, const char * argv[]) {
    int test_arr[10] = {1,0,4,3,2,8,5,9,6,7};
    swap_sort(test_arr, 10);
    for_each(test_arr,test_arr+10,[](int num){cout << num << " ";});
    cout << endl;
    std::cout << "Hello, World!\n";
    return 0;
}