数据结构&算法 合并排序

  • 合并排序

    合并排序是一种基于分治法的排序技术。最坏情况下的时间复杂度为Ο(nlogn),它是最受人遵从的算法之一。合并排序首先将数组分成相等的两半,然后以排序的方式将它们合并。
  • 合并排序如何工作?

    为了理解合并排序,我们采用未排序的数组,如下所示:
    mergesort
    我们知道合并排序首先将整个数组迭代地分成相等的一半,除非获得原子值。我们在这里看到一个由8个项目组成的数组分为两个大小为4的数组。
    mergesort
    这不会更改原件中项目出现的顺序。现在我们将这两个数组分为两半。
    mergesort
    我们进一步划分这些数组,并获得无法再划分的原子值。
    mergesort
    现在,我们将它们分解时的方式完全相同。请注意提供给这些列表的颜色代码。
    我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中。我们看到14和33处于排序位置。我们比较27和10,在2个值的目标列表中,我们先放置10,然后是27。我们更改19和35的顺序,而将42和44顺序放置。
    mergesort
    在合并阶段的下一个迭代中,我们比较两个数据值的列表,然后将它们合并为找到的数据值的列表,将所有数据按排序顺序放置。
    mergesort
    最终合并后,列表应如下所示:
    mergesort
    现在,我们应该学习合并排序的一些编程方面的知识。
  • 算法

    合并排序会继续将列表分为相等的一半,直到无法再对其进行划分为止。根据定义,如果它只是列表中的一个元素,则会对其进行排序。然后,合并排序将合并较小的排序列表,并将新列表也保持排序。
    
    步骤 1 − 如果它只是列表中已经排序的一个元素,返回。
    步骤 2 − 递归地将列表分成两半,直到不能再被分割为止。
    步骤 3 − 将较小的列表按照排序顺序合并到新的列表中。
    
  • 伪码

    现在我们将看到合并排序函数的伪代码。正如我们的算法指出的两个主要功能-分和合并。合并排序与递归一起工作,我们将以相同的方式看到实现。
    
    procedure mergesort( var a as array )
       if ( n == 1 ) return a
    
       var l1 as array = a[0] ... a[n/2]
       var l2 as array = a[n/2+1] ... a[n]
    
       l1 = mergesort( l1 )
       l2 = mergesort( l2 )
    
       return merge( l1, l2 )
    end procedure
    
    procedure merge( var a as array, var b as array )
    
       var c as array
       while ( a and b have elements )
          if ( a[0] > b[0] )
             add b[0] to the end of c
             remove b[0] from b
          else
             add a[0] to the end of c
             remove a[0] from a
          end if
       end while
       
       while ( a has elements )
          add a[0] to the end of c
          remove a[0] from a
       end while
       
       while ( b has elements )
          add b[0] to the end of c
          remove b[0] from b
       end while
       
       return c
      
    end procedure
    
  • 实现

    以下是C语言的实现
    
    #include <stdio.h>
    
    #define max 10
    
    int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
    int b[10];
    
    void merging(int low, int mid, int high) {
       int l1, l2, i;
    
       for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
          if(a[l1] <= a[l2])
             b[i] = a[l1++];
          else
             b[i] = a[l2++];
       }
       
       while(l1 <= mid)    
          b[i++] = a[l1++];
    
       while(l2 <= high)   
          b[i++] = a[l2++];
    
       for(i = low; i <= high; i++)
          a[i] = b[i];
    }
    
    void sort(int low, int high) {
       int mid;
       
       if(low < high) {
          mid = (low + high) / 2;
          sort(low, mid);
          sort(mid+1, high);
          merging(low, mid, high);
       } else { 
          return;
       }   
    }
    
    int main() { 
       int i;
    
       printf("List before sorting\n");
       
       for(i = 0; i <= max; i++)
          printf("%d ", a[i]);
    
       sort(0, max);
    
       printf("\nList after sorting\n");
       
       for(i = 0; i <= max; i++)
          printf("%d ", a[i]);
    }
    
    尝试一下