归并算法（高效）

1.什么是并归算法？

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列，简单的来说就是将两个有序子列合并成一个完全有序的子列

2.归并算法的实现

具体实现方法：将数组arr1的第一个元素与数组arr2的第一个元素比较，将较小的一个放入arr3中，然后将死一个元素较小的数组的下表向前加1，再将下标加1对应的元素的与较大的元素比较，将两者中较小的一个放入arr3中......一直到1或者2的数组中数组元素尽皆遍历结束，将剩下一个数组中剩下的元素放入arr3中

例如：1<2，将1放入arr3，下标加1，然后将6与2比较，2<6，将2放入arr3，下标加1，然后将3与6比较，3<6，将3放入arr3中，下标加1，再将4与6比较，4<6，将4放入arr3中，下标加1，再将10与6比较，6<10，将6放入arr3中，下标加1，再将8与10比较，将8放入arr3中，下标加1，再将9与10比较，9<10，将9放入arr3中，下标加1，再将46与10比较，10<46，将10放入arr3中，下标加1，将45与46比较，45<46，将45放入arr3中，下标加1，此时数组arr2已经完成，将arr1剩余的元素全部放入arr3中即可

#include<stdio.h>
int main()
{
  int arr1[5] = { 1,6,8,9,46 };
  int arr2[5] = { 2,3,4,10,45 };
  int arr3[10] = { 0 };
  int i = 0, j = 0, z = 0;
  while (i<5&&j<5)
  {
    if (arr1[i] > arr2[j])
    {
      arr3[z] = arr2[j];
      z++;
      j++;
    }
    else
    {
      arr3[z] = arr1[i];
      z++;
      i++;
    }
  }
  if (i == 5)
  {
    while (z < 10)
    {
      arr3[z] = arr2[j];
      z++;
      j++;
    }
  }
  if (j == 5)
  {
    while (z < 10)
    {
      arr3[z] = arr1[i];
      z++;
      i++;
    }
  }
  for (i = 0; i < 10; i++)
  {
    printf("%d ", arr3[i]);
  }
  return 0;
}

3.代码讲解

用i控制数组arr1,用j控制数组arr2,用z控制数组arr3，每当有一个元素进入数组arr3中时，将这个元素的下标加1，控制arr3数组的下标也加1。最后，分两种情况，分别对两种情况对应的数组剩余的元素桉顺序放入arr3数组中即可

4.总结

并归算法即可用于从小到大，也可用于从大到小的顺序，甚至中间有相等的数也可以进行处理，且效率和时间复杂度相对于我们常用的冒泡排序都有优势