應用合併排序邏輯

Question

我試圖解決我的使用合併排序得到以下情況下一個問題： 在n個元素的數組

得到一個陣列上的最低數字，然後拿到最大數目SO其減法（這些數字之間或差是最大的）

例如： N = 8 ARR {7,8,10,20,4,19,50,70} 我想要得到4和70，因爲他們的差別是66 如果我得到最低和最大的數字真的沒關係，我只關心他們減法中的最大差異。此外，第一個數字必須低於第二個數字，70和4是不允許的。

因爲這個問題需要我修改合併排序代碼，我在想：1）將所有數字分成1,2的數組）比較數組中的i號碼和i + 1號碼，如果我數字是最低的，然後得到它們的差異，並繼續在數組中的所有位置移動。

你覺得呢？我也遇到了設置基本情況的問題：S請幫忙！

Answer 1

合併排序的理念是將小部分的結果合併成更大的部分。

在合併排序中，首先將2個元素（1個元素的2個數組）合併爲2個元素的排序數組，然後將2個元素的2個排序數組合併成一個4個元素的排序數組（因爲2個數組被排序，只需要遍歷和比較，較小的元素總是以上升的順序排列在兩個數組中），然後將4個元素的2個排序數組合併成8個元素的排序數組。

 
| | | | | | | | | 
|sorted |  |  |  | 
|sorted   |    | 
|sorted       | 

現在，你只需要找到最大和最小的，因此，你只需要找到2個元素中的最大和最小。比較來自2個元素的2個數組中的2個最大元素並且找出更大的元素，然後比較來自4個元素的2個數組中的2個最大元素並且找到更大的元素，等等。 （同爲小了點。）

 
| | | | | | | | | 
|S  L|  |  |  | 
|Smllst Lrgst|    | 
|only need to care about S & L | 

換句話說，你不再排序整個數組，但發現的最大和最小和合並的結果得到最終的答案。

_{順便說一下，我認爲它有點像快速選擇快速排序。}

Answer 2

一個基本的合併排序排序你的數組，所以你很容易得到最大和最小的數字。但是你只是試圖修改數組，以便你只能得到最大和最小的數字 - 你不關心中間的數字。一旦你確定它們，它們就是有效的垃圾。

如何識別您正在查看的號碼是否無用？那麼，如果它是既不是最小也不是當前範圍中最大的數字。

首先查看合併排序的僞代碼。爲了更緊密地解決這個問題，你可以做出哪些最小的改變？