具有關於最終排序的數組額外的信息時，高效排序的整數數組

假設我們有這樣的整數數組稱爲data具有關於最終排序的數組額外的信息時，高效排序的整數數組

另外，我們有以下相同大小的數組稱爲info

info的每個值表示所述第一陣列上的索引。因此，例如，所述第一值是1這意味着0位置的最終排序陣列將具有值data[info[0]]。

通過遵循該邏輯的最終排序陣列將是以下：

data[info[0]] => 2 
data[info[1]] => 2 
data[info[2]] => 3 
data[info[3]] => 4 
data[info[4]] => 5

我想作的代替分選data陣列的，而無需使用大小N其中N的任何額外的存儲器是data陣列的大小。另外我希望總操作的數量儘可能小。

我一直想解決我的問題，但是我想不出任何東西，不會使用額外的內存。請記住，這些是我自己對我正在實施的系統的限制，如果這些限制不能保留，那麼我可能不得不考慮其他事情。

任何想法，將不勝感激。

預先感謝您

來源

2013-04-29 ksm001

你需要信息數組保持完整後排序（我猜不是因爲它被排序）？ – 2013-04-29 21:10:14

我不需要它保持完整。 – ksm001 2013-04-29 21:11:37

三個答案，並且沒有您的反饋？你確實說過「任何想法都會被讚賞」？是否有任何答案以任何方式幫助你？ :) – 2013-05-01 20:24:19

如果info陣列不需要保持完好，您可以使用額外的存儲和排序在O(n)：

for(int i = 0; i < n; ++i) { 
    int where = info[i]; 
    if (where == i) continue; 
    info[i] = data[i]; 
    data[i] = i < where ? data[where] : info[where]; 
}

如果data的元素已經在正確我們跳過那個索引。否則，記得info陣列中的元件，並且正確的元素寫入data，從data提取它，如果它來自一個更大的索引，以及從info如果它來自一個更小的索引。

當然，這種簡單的方法要求info和data陣列的類型是相同的，一般來說3*n副本。

如果data元素不能存儲在info數組中，我們可以按照週期中info：

for(int i = 0; i < n; ++i) { 
    // Check if this is already in the right place, if so mark as done 
    if (info[i] == i) info[i] = -1; 

    // Nothing to do if we already treated this index 
    if (info[i] < 0) continue; 

    // New cycle we haven't treated yet 
    Stuff temp = data[i]; // remember value 
    int j = info[i], k = i; 
    while(j != i) { 
     // copy the right value into data[k] 
     data[k] = data[j]; 
     // mark index k as done 
     info[k] = -1; 
     // get next indices 
     k = j; 
     j = info[j]; 
    } 
    // Now close the cycle 
    data[k] = temp; 
    info[k] = -1; 
}

那請問data元素，其中F是，已經是在元素的數量n - F + C副本在正確的地方（分揀置換固定點）和C是在分類排列長度> 1的循環的數目。這意味着副本數量最多爲3*n/2。

來源

2013-04-29 21:48:10

爲什麼不簡單'爲我在0..n-1：info [i]：= data [info [i]];'然後將元素從'info'複製回'data'？共2 * n'份。兩個數組的大小相同，均保存整數。（？） – 2013-04-30 11:30:28

過於複雜;）當我寫第一部分時，我有四分之三被循環追逐佔據。 – 2013-04-30 11:33:31

何不乾脆

for i in 0..n-1 : 
    info[i] := data[info[i]]

和info現在持有數組排序。如果一定要在data，只是複製回來，下一個：

for i in 0..n-1 : 
    data[i] := info[i]

2*n副本，整體。

來源

2013-04-30 15:25:15

具有關於最終排序的數組額外的信息時，高效排序的整數數組

回答

相關問題