算法之归并排序

文章目录

• 一、归并排序（递归版）
• 二、归并排序（非递归版）

  ---

  一、归并排序（递归版）

  归并排序思想：将数组划分为两个区间，左区间，右区间 然后对这两个区间内容进行排序 ，这两个区间排好序之后再将其合并为一个有序的区间

  

  这两个区间排好序之后，再将这两个区间合并为一个区间 也就是将这两个区间的数据排序为一个有序的区间

  而将数组划分为两个区间之后是如何将这两个区间里的内容排好序的呢 是重复同样的操 作再将这两个区间中的左区间分别又划分为两个区间（左区间，右区间）

  ，将这两个区间分别排好序之后，

  再归为一个区间，也就是左区间有序了，然后再排它的右区间，此时它的右区间右划分为两个区间（左区间，右区间）

  对它们分别进行排序 ，而划分下去的左右区间又要执行同样的操作，直到最后区间大小为一时，那么此时就不用排返回，返回时与另一个区间比较进行排序，

  最后右区间变为有序的了，最后将这两个大的左右区间归并排序为一个区间，此时这个区间有序 ，由于递归排序回来时，将小区间排好序，最后整个大区间跟着有序了

  我上图只是画了整个数组左区间的，右区间可以下去尝试下，右区间也是如此

  void _MergeSort(int* a, int left, int right, int* tmp)
  {
  	//当区间中只有一个数时就不用再对其进行排序
  	if (left >= right)
  		return;
  	//每次将其区间折半划分为左区间和右区间
  	int mid = (left + right) / 2;
  	//再重复划分，直到它的左右区间只剩下一个数，那么再返回
  	//对其排序
  	_MergeSort(a, left, mid, tmp);
  	_MergeSort(a, mid + 1, right, tmp);
  	//将其小区间排好序后再排它的大区间
  	//小区间有序之后大区间排过来也就是有序的了
  	int begin1 = left, end1 = mid;
  	int begin2 = mid + 1, end2 = right;
  	int begin = left;
  	//将左右区间合并为一个区间
  	while (begin1 
  		if (a[begin1]  a[begin2])
  		{
  			tmp[begin++] = a[begin2++];
  		}
  		else
  		{
  			tmp[begin++] = a[begin1++];
  		}
  	}
      
      //两个区间中还剩余数据的那个区间直接尾插到tmp数组后面
  	while (begin1 
  		tmp[begin++] = a[begin1++];
  	}
  	while (begin2 
  		tmp[begin++] = a[begin2++];
  	}
  	//最后将排好序的区间拷贝回原来的数组
  	memcpy(a + left, tmp+left, sizeof(int)*(right - left + 1));
  }
  void MergeSort(int* a, int n)
  {
  	//开一个临时数组用来存放小区间排序后的数据
  	//最后再将排序后的数组拷贝回原数组中
  	int* tmp = (int*)malloc(sizeof(int) * n);
  	if (tmp == NULL)
  	{
  		perror("malloc fail\n");
  		return;
  	}
  	//归并排序分两区间进行
  	_MergeSort(a, 0, n - 1, tmp);
  	free(tmp);
  }
  
  	int* tmp = (int*)malloc(sizeof(int) * n);
  	if (tmp == NULL)
  	{
  		perror("malloc fail\n");
  		return;
  	}
  	int gap = 1;
  	while (gap =n )
  			{
  				end2 = n - 1;
  			}
               //两个区间中小的数尾插到tmp数组中
  			while (begin1 
  				if (a[begin1]