合併已排序陣列的 JavaScript

---

在 javascript 中合併已排序的陣列可以使用資料結構中提供的排序技術來完成。在這個問題中，我們將得到兩個已排序的陣列，我們需要將它們合併。合併後，返回一個也是已排序形式的單個數組。

為了解決這個問題，我們將使用貪心演算法。

什麼是已排序陣列？

在 javascript 中，陣列是相似資料型別的集合，我們可以在執行時調整陣列的大小。已排序陣列是陣列項的順序形式。它們的順序應該按升序排列。在 javascript 中，有一個預定義的方法叫做 sort() 用於對陣列中存在的元素進行排序。預設情況下，sort() 方法按升序排列元素。

// array before sorting
var arr = [2, 5, 1, 3, 6, 9, 7]

//array after sorting
var arr = [1, 2, 3, 5, 6, 7, 9]

理解問題

為了解決這個問題，我們將建立一個函式，並將兩個陣列作為引數傳遞。這些陣列已經處於排序形式。我們需要將它們合併到一個數組中。

在函式的第一步，它將比較兩個已排序陣列的元素，並將最小的元素新增到新建立的陣列的第 0 個索引處。在此步驟之後，它將增加指標並再次比較下一個數字，並將其新增到下一個索引處。

我們將在其中遵循自上而下方法的貪婪方法中使用貪婪演算法。資料結構中的貪婪方法基本上是透過選擇在特定時刻可用的最佳選項來解決問題的。為了更好地理解，讓我們看下面的例子

演算法

要將兩個給定的已排序數組合併到一個已排序陣列中，我們可以使用此演算法。因此，分步過程如下

步驟 1：在第一步中，定義兩個已排序陣列。

步驟 2：定義一個名為 merge2Arrays 的函式。並在其中傳遞兩個變數。

步驟 3：使用給定的 mergedArray 建立一個空結果陣列，以將合併的陣列儲存在其中。

步驟 4：在此步驟中，我們將初始化指標 a、b 和 current 以瞭解陣列中每個元素的位置。這裡“a”是第一個陣列的索引位置，“b”是第二個陣列的索引值，而 current 是新合併陣列的索引值。

步驟 5：在此步驟中，我們將初始化一個 while 迴圈。它將執行到兩個陣列的長度。

步驟 6：現在初始化 2 個變數並分別命名為 unmerge1 和 unmerge2。這些變數將儲存前面定義的每個陣列的跟蹤項。

步驟 7：使用索引“a”和“b”比較 unmerge1 和 unmerge2 的值。如果 unmerge1 的值小於 unmerge2，則將 unmerge1 新增到 mergedArray[current] 中。並將“a”的計數增加 1。

步驟 8：現在在 else 部分，如果 unmerge2 的值小於 unmerge1，則將 unmerge2 新增到 mergedArray[current] 中，並將“b”的計數增加 1。

步驟 9：在 if-else 塊之外，將“current”的計數增加 1。

步驟 10：在此步驟中返回 mergedArray 值。

步驟 11：然後呼叫步驟 2 中定義的函式並控制檯輸出以檢視。

示例

// Declaration of two sorted arrays
var array1 = [12, 16, 17, 11, 13];
var array2 = [10, 13, 15, 29, 25];


//define function to merge arrays
function merge2Arrays(array1, array2) {
  let mergedArray = [];
  let a = 0;
  let b = 0;
  let current = 0;

//running a while loop until all elements get sorted
  while (current < ( array1.length + array2.length )) {
     let unmerge1 = array1[a];
     let unmerge2 = array2[b];

     // if next element comes from array1
     if (unmerge1 < unmerge2) {
        mergedArray[current] = unmerge1;
        a++;

     // if next element comes from array2
     } else {
        mergedArray[current] = unmerge2;
        b++;
     }

     current++;
  }

  // return merged array
  return mergedArray;
}

//calling merge2Array function
merge2Arrays(array1, array2);

console.log("Before Merging:")
console.log(array1);
console.log(array2);
console.log("After Merging")
console.log (merge2Arrays(array1, array2));

在上面的程式碼中，我們首先定義了兩個按排序順序排列的陣列，分別命名為 array1 和 array2。之後，我們定義了一個名為 merge2Arrays 的函式，它將這兩個定義的陣列作為引數。之後，mergeArray 初始化為空陣列以儲存結果排序陣列。

然後將 3 個變數 a、b 和 current 初始化為 0，它們將作為 array1 和 array2 以及 mergedArray 的索引值。然後我們初始化了一個 while 迴圈來檢查最小元素。迴圈將執行直到所有元素都排序。最後，返回排序陣列的值。

輸出

Before:
[ 12, 16, 17, 11, 13 ]
[ 10, 13, 15, 29, 25 ]
After:
[ 10, 12, 13, 15, 16, 17, 11, 13, 29, 25]

時間複雜度

在 while 迴圈的每次迭代中，程式使用 unmerge1 和 unmerge2 比較兩個輸入陣列中當前元素的值。然後選擇較小的值新增到 mergedArray 中。然後在需要時增加每個計數器值。

while 迴圈迭代直到 array1 的長度和 array2 的長度的總和倍。由於迴圈的每次迭代都會向 mergedArray 新增一個元素，並且陣列包含 array1 和 array2 元素的總數。迴圈內的比較和指標增量需要恆定時間，因此該演算法的整體時間複雜度為 O(N)，其中 N 是 n 和 m 的總和。這裡 n 是 array1 的長度，m 是 array2 的長度。

結論

透過此實現，我們學習瞭如何使用貪心演算法對兩個已排序陣列進行排序。貪心演算法基本上遵循自上而下的方法。此技術稱為合併排序，因為它將兩個數組合併到一個已排序陣列中。並且我們學習瞭如何計算該演算法的時間複雜度，即 O(n+k) 或 O(N)。