以有效的方式對兩個數組進行排序和合並？

我們有兩個陣列（未排序），容量爲n和n + m。第一個數組有n元素。第二個陣列有m元素（另外還有n保留給更多元素的位置）。以有效的方式對兩個數組進行排序和合並？

目標是合併兩個數組，並以排序的方式將結果存儲在第二個數組中，而不使用額外的空間。

目前，我使用快速排序對兩個數組進行排序，然後使用合併排序合併它們。有沒有更有效的方法來實現這一目標？

來源

2013-04-23 Pixel

如果這是家庭作業，那很好，但你應該這樣說。你試過什麼了？ – Sepster 2013-04-23 11:47:38

第二個數組的大小是多少？ 'n'或'n + m'，你到現在爲止嘗試過什麼？ – SuperSaiyan 2013-04-23 11:47:42

@Thrustmaster大小n + m，包含m個元素。 – Sepster 2013-04-23 11:48:43

您可以探索合並排序。

https://www.google.com/search?q=mergesort&ie=UTF-8&oe=UTF-8&hl=en&client=safari#itp=open0

或者根據大小，可以將每個陣列上做快速排序，然後使用合併排序技術將它們合併（或合併，然後快速排序）。

我會去歸併，它基本的工作原理是單獨排序每個陣列，然後它把它們放在一起，以便

您正在尋找O（nlogn）的歸併和O（nlogn）的快速排序，但可能的O（n^2）與quicksort最壞的情況。

來源

2013-04-23 11:48:14

合併排序也可以作爲穩定的算法實現，因此您可以保持相對順序。快速排序不會這樣做 – 2013-04-23 11:57:39

mergesort需要O（n）額外空間 – malejpavouk 2013-04-23 12:02:27

然後使用快速排序。或者，使用AVL樹作爲數據結構，並執行中綴列印（O（n））排序 – 2013-04-23 12:03:31

如果在第二陣列存儲，比您正在使用額外的空間，但是你可以通過幫助像這樣的GC最小化：

在第二陣列
都設置加入兩個數組以前的變量爲空，使他們有資格被垃圾收集
排序所述第二陣列，Arrays.sort(...) - 爲O（n LOG（n））的

看的Javadoc此方法：

/** 
    * Sorts the specified array into ascending numerical order. 
    * 
    * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort 
    * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm 
    * offers O(n log(n)) performance on many data sets that cause other 
    * quicksorts to degrade to quadratic performance, and is typically 
    * faster than traditional (one-pivot) Quicksort implementations. 
    * 
    * @param a the array to be sorted 
    */ 
    public static void sort(int[] a) {

來源

2013-04-23 12:06:04 cahen

，如果我想也保證爲O（n *日誌（n））的行爲，我會用的Heapsort修改後的版本，它會使用兩個陣列作爲堆的基礎，並將排序的數據存儲在數組的附加部分。

這也可能比兩個Quicksorts更快，因爲它不需要額外的合併操作。此外Quicksort速度非常緩慢，當小陣列正在排序（問題的大小沒有提到問題的設置）。

來源

2013-04-23 12:11:22 malejpavouk

我們把小陣列稱爲N陣列，將另一個稱爲M陣列。我假設M數組的元素最初位於0到m-1的位置。使用您最喜歡的技術對兩個陣列進行排序，這可能取決於其他標準，如穩定性或限制最壞情況的行爲。

if min(N) > max(M) 
    copy N's elements over starting at location m [O(n) time] 
else 
    move M's elements to the end of the M array (last down to first) [O(m) time] 
    if min(M) > max(N) 
     copy N's elements over starting at location 0 [O(n) time for the copy] 
    else 
     perform classic merge: min of remaining m's and n's gets migrated 
     to next available space in M [O(min(m,n) time]

總的來說，這是由初始排序時間占主導地位，合併階段都是線性的。將m移動到M數組的末尾可以保證沒有空間衝突，因此您不需要按照您的規範額外存儲側面存儲。

來源

2013-04-23 14:46:10 pjs

顯然做的最好的事情是N的內容複製到N + M陣列中的自由空間和快速排序的N + M陣列。

這樣做2個快速排序，然後合併排序，你只是使整個操作效率較低。

這裏是一個腦力鍛鍊，如果你有排序長度M的數組，你會分裂成2個數組，M1和M2，每個排序，然後歸併排序在一起？不可以。如果你這樣做，你只會限制每次快速撥號的信息，從而減慢過程。

那麼，爲什麼你把你的兩個首發陣列分開？

來源

2013-04-23 15:25:07

+1排序，因爲它更加直接和無憂無慮。雖然，因爲它是功課，可能不是被查找的東西，但似乎這是一般應該做的。 – Nuclearman 2013-04-23 20:59:39

以有效的方式對兩個數組進行排序和合並？

回答

相關問題