查看原文
其他

漫画:什么是归并排序?

小灰 程序员小灰 2019-12-26



—————  第二天  —————







————————————










举个例子,有A、B、C、D、E、F、G、H一共8个武术家参考参加比武大会。


第一轮,两两一组,有4名选手胜出(四分之一决赛)


第二轮,两两一组,有两名选手胜出(半决赛)


第三轮,仅剩的两人一组,冠军胜出(总决赛)





归并排序和擂台赛,有什么相同和不同之处呢?让我们以下面这个数组来举例说明:



归并排序就像是组织一场元素之间的“比武大会”,这场比武大会分成两个阶段:


1.分组

假设集合一共有n个元素,算法将会对集合进行逐层的折半分组。


第一层分成两个大组,每组n/2个元素;

第二层分成4个小组,每组n/4个元素;

第三层分成8个更小的组,每组n/8个元素;

......

一直到每组只有一个元素为止。


这样一来,整个数组就分成了一个个小小的“擂台”。




2.归并

既然分了组,接下来就要开始“比武”了。


归并排序和擂台赛有一个很大的不同,就是擂台赛只需要决定谁是老大,而并不关心谁做老二和老三;归并排序的要求复杂一些,需要确定每一个元素的排列位置。


因此,当每个小组内部比较出先后顺序以后,小组之间会展开进一步的比较和排序,合并成一个大组;大组之间继续比较和排序,再合并成更大的组......最终,所有元素合并成了一个有序的集合。




这个比较与合并的过程叫做归并,对应英文单词merge,这正是归并排序名字的由来。




归并操作需要哪三个步骤呢?我们以两个长度为4的集合为例:



第一步,创建一个额外大集合用于存储归并结果,长度是两个小集合之和。(p1,p2,p是三个辅助指针,用于记录当前操作的位置)



第二步,从左到右逐一比较两个小集合中的元素,把较小的元素优先放入大集合。


由于1<2,所以把元素1放入大集合,p1和p各右移一位:



由于2<3,所以把元素2放入大集合,p2和p各右移一位:



由于3<7,所以把元素3放入大集合,p1和p各右移一位:


由于5<7,所以把元素5放入大集合,p1和p各右移一位:



由于6<7,所以把元素6放入大集合,p1和p各右移一位:



此时左侧的小集合已经没有元素可用了。


第三步,从另一个还有剩余元素的集合中,把剩余元素按顺序复制到大集合尾部。



这样一来,两个有序的小集合就归并成了一个有序的大集合。



  1. static public void mergeSort(int[] array, int start, int end){

  2. if(start < end){

  3. //折半成两个小集合,分别进行递归

  4. int mid=(start+end)/2;

  5. mergeSort(array, start, mid);

  6. mergeSort(array, mid+1, end);

  7. //把两个有序小集合,归并成一个大集合

  8. merge(array, start, mid, end);

  9. }

  10. }



  1. static private void merge(int[] array, int start, int mid, int end){

  2. //开辟额外大集合,设置指针

  3. int[] tempArray = new int[end-start+1];

  4. int p1=start, p2=mid+1, p=0;

  5. //比较两个小集合的元素,依次放入大集合

  6. while(p1<=mid && p2<=end){

  7. if(array[p1]<=array[p2])

  8. tempArray[p++]=array[p1++];

  9. else

  10. tempArray[p++]=array[p2++];

  11. }

  12. //左侧小集合还有剩余,依次放入大集合尾部

  13. while(p1<=mid)

  14. tempArray[p++]=array[p1++];

  15. //右侧小集合还有剩余,依次放入大集合尾部

  16. while(p2<=end)

  17. tempArray[p++]=array[p2++];

  18. //把大集合的元素复制回原数组

  19. for (int i=0; i<tempArray.length; i++)

  20. array[i+start]=tempArray[i];

  21. }



  1. public static void main(String[] args) {

  2. int[] array = { 5, 8, 6, 3, 9, 2, 1, 7 };

  3. mergeSort(array, 0, array.length-1);

  4. System.out.println(Arrays.toString(array));

  5. }













—————END—————




喜欢本文的朋友,欢迎关注公众号 程序员小灰,收看更多精彩内容



欢迎长按二维码关注 小灰学英语,你所学到的不只是英语!



给个[在看],是对小灰最大的支持!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存