归并排序

来自计算思维百科
跳转至: 导航搜索

如果我们希望对很多数据按照从小到大或是从大到小的顺序重新放置,这就是排序将。归并排序是一种高效的排序方法,它的基本思想是将两个或两个以上的元素有序序列组合,使其成为一个新的有序序列。

基本概念

归并排序的基本思想是:假设元素的个数是n,将每个元素作为一个有序的子序列,然后将相邻的两个子序列两两合并,得到|n/2|个长度为2的有序子序列,每个子序列都是排好序的。继续将相邻的两个子序列两两合并,得到|n/4|个长度为4的有序子序列,每个子序列也是排好序的。依次类推,重复执行以上操作,直到有序序列合并为1个为止。这样就得到了一个有序序列。

应用范围

各种需要排序的情况都可以应用归并排序。

使用方法及步骤

  1. 将每个数据看做一个有序的子序列;
  2. 将两两子序列合并为新的有序子序列;
  3. 重复2,直至只有一个序列。

应用案例

应用1- 数字排序

案例:有一组数字序列:37,19,43,22,57,89,26,92,归并排序过程如下:

序号:    1   2    3   4     5    6    7    8

初始状态:【37】,【19】,【43】,【22】,【57】,【89】,【26】,【92】

 

第一趟归并结果:【19     37】,【22     43】,【57    89】,【26     92】

 

第二趟归并结果:   【19  22  37   43】,    【26   57   89    92】

 

第三趟归并结果:        【19  22  26  37  43  57  89  92】

应用2-小组讨论

案例:选修课上老师让同学们分组讨论,每个同学先在纸上写下自己的观点,同桌的两个同学一起讨论比较,选出两个人中比较好的答案。前后两组同学再进行比较,选出前4名同学中最好的答案。依次类推,直到选出全班最好的答案。

这个过程就类似于归并排序,每次选取相邻的两个子序列合并为一个子序列,直到整个序列成为有序序列。

可以体现的计算思维

归并排序的主要思想就是分治法,将一个规模为N的排序问题分解为N/2个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解,提现了计算思维的递归特点。