合并排序

合并排序 首页 / 结构和算法入门教程 / 合并排序

合并排序是一种基于分而治之的排序技术,最坏情况下的时间复杂度为Ο(n log n),合并排序首先将数组分成相等的两半,然后以排序的方式将它们合并。

合并排序

为了理解合并排序,我们采用未排序的数组,如下所示:

Unsorted Array

我们知道合并排序首先将整个数组迭代地分成相等的一半,除非获得原子值。我们在这里看到一个由8个元素组成的数组分为两个大小为4的数组。

Merge Sort Division

这不会更改原件中元素出现的顺序。现在我们将这两个数组分为两半。

Merge Sort Division

我们进一步划分这些数组,并获得无法再划分的原子值。

Merge Sort Division

现在,我们将它们分解时的方式完全相同。请注意提供给这些列表的颜色代码。

无涯教程网

我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中。我们看到14和33处于排序位置。我们比较27和10,在2个值的目标列表中,我们先放置10,然后是27。我们更改19和35的顺序,而将42和44顺序放置。

Merge Sort Combine

在合并阶段的下一个迭代中,我们比较两个数据值的列表,然后将它们合并为找到的数据值的列表,将所有数据按排序顺序放置。

Merge Sort Combine

最终合并后,列表应如下所示:

Merge Sort

现在,我们应该学习合并排序的一些编程方面的知识。

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/merge-sort-algorithm.html

来源:LearnFk无涯教程网

伪代码

现在我们将看到合并排序函数的伪代码,正如我们的算法指出的两个主要函数-分和合并。

合并排序与递归一起工作,我们将以相同的方式看到实现。

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]);
}
List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

零基础学Java -〔臧萌〕

TypeScript开发实战 -〔梁宵〕

Electron开发实战 -〔邓耀龙〕

代码之丑 -〔郑晔〕

反爬虫兵法演绎20讲 -〔DS Hunter〕

深入浅出分布式技术原理 -〔陈现麟〕

快手 · 移动端音视频开发实战 -〔展晓凯〕

深入拆解消息队列47讲 -〔许文强〕

结构执行力 -〔李忠秋〕

好记忆不如烂笔头。留下您的足迹吧 :)