資料結構中的合併演算法

合併演算法用於將兩個排序列表合併到一個列表中。可以在不同的情況下使用該演算法。如果要執行合併排序，則需要將分類列表合併到更大的列表中。

方法很簡單。我們使用兩個列表，其中包含兩個指標。第一個指標指向第一個列表中的元素，第二個指標指向第二個列表中的元素。根據它們的值，從這兩個列表中取出較小的元素，然後增加該對應列表的指標。此操作將一直執行，直到其中一個列表用完。然後，將剩餘的列表新增到最終合併列表的末尾。

讓我們看看說明以獲得更好的主意。

演算法

Merge(array, left, middle, right) −

Begin
   nLeft := m - left+1
   nRight := right – m
   define arrays leftArr and rightArr of size nLeft and nRight respectively
   for i := 0 to nLeft do
      leftArr[i] := array[left +1]
   done
   for j := 0 to nRight do
      rightArr[j] := array[middle + j +1]
   done
   i := 0, j := 0, k := left
   while i < nLeft AND j < nRight do
      if leftArr[i] <= rightArr[j] then
         array[k] = leftArr[i]
         i := i+1
      else
         array[k] = rightArr[j]
         j := j+1
         k := k+1
      done
   while i < nLeft do
      array[k] := leftArr[i]
      i := i+1
      k := k+1
   done
   while j < nRight do
      array[k] := rightArr[j]
      j := j+1
      k := k+1
   done
End

更新於：11-8-2020

634 次瀏覽

開啟你的 職業生涯

完成課程，獲得認證

開始
廣告