排序合併數組組成的排序陣列

我有兩個排序的數組，例如（3,4,5）和（1,3,7,8），我得到了組合的排序數組（3,4,5,1,3,7,8）。排序合併數組組成的排序陣列

現在我想對已經組合的數組進行排序，而不是分割它，而是通過覆蓋它，通過使用它由2個已經排序的數組組成的事實。有沒有辦法有效地做到這一點？我知道有很多關於如何做到這一點的線程，方法是迭代排序後的數組，然後相應地將值放入新數組中，但我還沒有在任何地方看到過這種類型的問題。我想在c中這樣做，但任何幫助/僞代碼將非常感激。謝謝！

編輯：將執行排序的函數只會給出組合數組和（如果需要的話）其他兩個數組的長度（可能）。

來源

2016-11-16 SoflolikeAntonio

相反支出有很多時間對已經合併的數組進行排序，那麼改變當前拋出兩個數組到單個數組中的代碼是不是會容易得多？你知道，那個代碼可以簡單地進行合併，同時建立新的數組？而不是先將兩個數組合併成一個，然後計算如何有效地重新排序。 – GhostCat

我不明白你的意思。你的意思是覆蓋和不吐口水？爲什麼標準的快速或預先分類將不適用於您的情況？ – Sigstop

@Sigstop我想他想說：我有一個數組，它由兩個有序數字序列組成。有沒有一種方法根據這種知識對數組進行排序......沒有做出「真正的」排序;並且不會創建另一個新陣列。 – GhostCat

如果你已經有原始的排序陣列，組合陣列（注意它是而不是排序）沒有真正的幫助，除了你的目標存儲已分配。

有一個衆所周知的，非常簡單的算法來合併兩個排序的範圍，但您可以使用std::merge而不是自己編碼。

注意，僅適用於非重疊輸入&輸出範圍：爲您的修改問題，使用std::inplace_merge，與中間的迭代器從你的第二個序列設定爲第一個元素：

void sort_combined(int *array, size_t total, size_t first) { 
    std::inplace_merge(array, array + first, array + total); 
} 

// and use it like 

int combined[] = {3, 4, 5, 1, 3, 7, 8}; 
const size_t first = 3; 
const size_t second = 4; 
const size_t total = 7; // == sizeof(combined)/sizeof(*combined) 

sort_combined(combined, total, first);

來源

2016-11-16 13:30:52 Useless

排序合併數組組成的排序陣列

回答

相關問題