数据结构中的合并算法

合并算法用于将两个排序列表合并到一个列表中。可以在不同的情况下使用该算法。如果要执行合并排序，则需要将分类列表合并到更大的列表中。

方法很简单。我们使用两个列表，其中包含两个指针。第一个指针指向第一个列表中的元素，第二个指针指向第二个列表中的元素。根据它们的值，从这两个列表中取出较小的元素，然后增加该对应列表的指针。此操作将一直执行，直到其中一个列表用完。然后，将剩余的列表添加到最终合并列表的末尾。

让我们看看说明以获得更好的主意。

算法

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 次浏览

开启你的 职业生涯

完成课程，获得认证

开始
广告