归并排序 C语言
 
思路：分治 先分原数组左半边 再分原数组右半边，最终层层递归治实现排序；图片来自https://blog.csdn.net/baidu_15547923/article/details/89742717
 归并与逆序对的关系：以分治的某一个阶段为例
 　　　　　　　[下标]　　　0123　　　　 4567　
 　　　　　　　[数组]　　　4578 　　　　1236
 　　　　　　　（ start=0， mid=3， end=7 ）
 　　左半边 4 > 1就代表一对逆序对，而左半边已经排序完成，即(4,1)、(5,1)、(7,1)、(8,1)都是逆序对，
 　　同理4>2，逆序对有(4,2)、(5,2)、(7,2)、(8,2)…(4,3)、(5,3)、(7,3)、(8,3)…(7,6)、(8,6)；最终当左侧大于右侧时，逆序对个数可表达mid-i+1(i为左侧索引，mid为左侧索引的结尾)
 　　LeetCode题型：
 　　LeetCode 493 翻转对
 　　https://blog.csdn.net/qq_40405527/article/details/108074965
 　　LeetCode 327 区间和的个数
 　　https://blog.csdn.net/qq_40405527/article/details/108085048
 
 
#include<stdio.h>
#include<stdlib.h>
#define ArrLen 20
void printList(int *nums, int len) {
	int i;
	for (i = 0; i < len; i++) {
		printf("%d ", nums[i]);
	}
}
void merge(int *nums, int start, int mid, int end) {//治
	int len=end-start+1;
    int * temp=(int *)malloc(sizeof(int)*len);
	int k = 0;
	int i = start;
	int j = mid + 1;
	while (i <= mid && j <= end) {//注意区间的连贯性0~mid mid+1~end
		if (nums[i] < nums[j]){    //或i=start;j=mid; while(i<mid && j<=end)
			temp[k++] = nums[i++];
        }
		else{
			temp[k++] = nums[j++];
        }
	}
	if (i == mid + 1) {
		while(j <= end)
			temp[k++] = nums[j++];
	}
	if (j == end + 1) {
		while (i <= mid)
			temp[k++] = nums[i++];
	}
	for (j = 0, i = start ; j < k; i++, j++) {
		nums[i] = temp[j];
	}
    free(temp);
    temp=NULL;
}
 
void mergeSort(int *nums, int start, int end) {
#if 0	
    if (start >= end)
		return;
	int mid = ( start + end ) / 2;
	mergeSort(nums, start, mid);//分 递归划分原数组左半边
	mergeSort(nums, mid + 1, end);//递归划分右半边if
	merge(nums, start, mid, end);//合并
#endif
    if(start<end){
         int mid = (start + end)/2;
         mergeSort(nums,start,mid);
         mergeSort(nums,mid+1,end);
         merge(nums,start,mid,end);
    }
} 
void main(){
	int nums[] = {4, 7, 6, 5, 2, 1, 8, 2, 9, 1};
    int len=sizeof(nums)/sizeof(int);
	mergeSort(nums, 0, len);
	printList(nums, len);
}

 
归并排序
 
具体代码
过程分析
性能分析

 
具体代码
 
#include<stdio.h>

//将两个有序数组合并的过程
void Merge(int* R, int start, int mid, int end)
{
	//需要把元素全誊到这个新数组去
	int A[end-start+1];
	//i代表第一个有序数组的起始位置
	int i = start;
	//j代表第二个有序数组的起始位置
	int j = mid+1;
	//k用来逐个表示A数组中的元素
	int k = 0;

	//从这两个有序数组中找出小的，逐个放入A数组
	while(i<=mid && j<=end)
	{
		//j的小就放j
		if(R[i]>R[j])
		{
			A[k] = R[j];
			j++;
		}
		else
		{
			A[k] = R[i];
			i++;
		}
		k++;
	}
	
	//当出现某个数组放完了之后，直接把另一个数组剩下的全放入A即可
	//其实下面那两个if可以不写，只不过这里只是增强可读性而已....
	if(i>mid)
	{
		while(j<=end)
		{
			A[k] = R[j];
			j++;
			k++;
		}		
	}
	if(j>end)
	{
		while(i<=mid)
		{
			A[k] = R[i];
			i++;
			k++;
		}		
	}
	
	//然后再把已经有序了的元素装回到原来啊的R数组
	for(int m = 0;m<k;m++)
	{
		R[start] = A[m];
		start++;
	}
}

//归并排序
void MergeSort(int* R, int start, int end) 
{
	//如果没把数组分到单个元素，就一直分治
	if(start<end)
	{
		//一分为二
		int mid = (start+end)/2;
		//左右两边排好序
		MergeSort(R,start,mid);
		MergeSort(R,mid+1,end);
		//拼接到一起
		Merge(R,start,mid,end);
	}
}

int main()
{
	int M[6] = {1,5,3,7,8,2};
	MergeSort(M,0,5);
	for(int i=0;i<6;i++)
	{
		printf("%d  ", M[i]);	
	}
}

 
过程分析
 
这是冯诺依曼大佬提出的算法，利用了分治的思想，各层分治递归可以同时进行。所以我连分步解释的图都不好画了。。。。。。
 不过总体流程大概是这样：
 
 这个算法的主体思路就是把一个数组全部划分成单个元素，单个元素进行比较后合并。由于是递归，多个比较同时发生，所以会更快。每次在比较完后，会得到两个有序数组，只需要将有序数组合并即可（对于只用单个元素的情况，就是直接比大小了）。
 我这里就只讲一下合并步骤的思路了。
 
合并步骤
 
1.得到两个有序数组，但是他们在空间上是连在一起的，他们以你之前划分的标准mid元素来分界。
 2.所以两个数组的空间位置分别是
 start—mid， mid+1—end-1
 准备好指针，开始排序即可
 3.由于他们的都是有序数组，从头逐个比较，取走小的那个即可。
 比如：
 A数组-----------1，6，7，9，9
 B数组-----------2，3，4，5，8
 那么我们先从A中取走1，再比较A的第二个元素和B的第一个元素，取走2，同理，继续比较，取走B中的3，然后4，然后5，然后再取A中的7，再取B中的。
 4.这时，B数组已经取完了，只需要把剩下的A中的两个9全部放到数组里即可。
 5.最后注意我们是把数组先有序地誊到一个空的数组里了，还要放回来，完成。
 
性能分析
 

 
#include 
 
#include 
 
void splitArrays();
 
void sortArrays(int num[], int start, int mid, int end);
 
int main(int argc, const char * argv[])
 
{
 
int num_really[11];
 
for (int i = 0; i < 11; i++) {
 
num_really[i] = arc4random() % (90 - 10 + 1) + 10;
 
}
 
for (int i = 0; i < 11; i++) {
 
printf("%d ", num_really[i]);
 
}
 
printf("\n");
 
splitArrays(num_really, 0, 10);
 
for (int i = 0; i < 11; i++) {
 
printf("%d ", num_really[i]);
 
}
 
printf("\n");
 
return 0;
 
}
 
void splitArrays(int num[], int start, int end) {
 
int mid = (start + end) / 2;
 
if (mid != start) {
 
splitArrays(num, start, mid);
 
splitArrays(num, mid + 1, end);
 
sortArrays(num, start, mid, end);
 
} else {
 
sortArrays(num, start, mid, end);
 
}
 
}
 
void sortArrays(int num[], int start, int mid, int end) {
 
int num_left[mid - start + 1];
 
int num_right[end - mid];
 
//复制左子列
 
for (int i = 0; i < mid - start + 1; i++) {
 
num_left[i] = num[start + i];
 
}
 
//复制右子列
 
for (int i = 0; i < end - mid; i++) {
 
num_right[i] = num[mid + 1 + i];
 
}
 
int l_start = 0;
 
int l_end = mid - start + 1;
 
int r_start = 0;
 
int r_end = end - mid;
 
int sign = start;
 
while (l_start < l_end && r_start < r_end) {
 
if (num_right[r_start] < num_left[l_start]) {
 
num[sign] = num_right[r_start];
 
r_start++;
 
} else {
 
num[sign] = num_left[l_start];
 
l_start++;
 
}
 
sign++;
 
}
 
//对于子列最后几个的处理
 
if (l_start == l_end) {
 
for (r_start; r_start < r_end; r_start++) {
 
num[sign] = num_right[r_start];
 
sign++;
 
}
 
} else if (r_start == r_end) {
 
for (l_start; l_start < l_end; l_start++) {
 
num[sign] = num_left[l_start];
 
sign++;
 
}
 
}
 
}

归并排序
 
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法
 算法复杂度：O（nlogn）
 就是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
 
 递归实现
 
/* 归并排序 - 递归实现 */

#include <stdio.h>
#include<stdlib.h> 
#define ElementType int



/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */ 
     int Center;
     
     if ( L < RightEnd ) {
          Center = (L+RightEnd) / 2;
          Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
          Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
          Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
     }
}

void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
     ElementType *TmpA;
     TmpA = (ElementType *)malloc(N*sizeof(ElementType));
     
     if ( TmpA != NULL ) {
          Msort( A, TmpA, 0, N-1 );
          free( TmpA );
     }
     else printf( "空间不足" );
}


int main()
{
	int A[5]={4,5,3,3,2};
	MergeSort(A,5);
	for(int i=0;i<5;++i)
	{
		printf("%d ",A[i]);
	}
	return 0;
}
 
迭代实现
 
#include <stdio.h>
#include<stdlib.h> 
#define ElementType int

/* 归并排序 - 迭代实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
     int LeftEnd, NumElements, Tmp;
     int i;
     
     LeftEnd = R - 1; /* 左边终点位置 */
     Tmp = L;         /* 有序序列的起始位置 */
     NumElements = RightEnd - L + 1;
     
     while( L <= LeftEnd && R <= RightEnd ) {
         if ( A[L] <= A[R] )
             TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
         else
             TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
     }

     while( L <= LeftEnd )
         TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
     while( R <= RightEnd )
         TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
         
     for( i = 0; i < NumElements; i++, RightEnd -- )
         A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}


/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;
      
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

void Merge_Sort( ElementType A[], int N )
{ 
     int length; 
     ElementType *TmpA;
     
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( ElementType ) );
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              length *= 2;
              Merge_pass( TmpA, A, N, length );
              length *= 2;
          }
          free( TmpA );
     }
     else printf( "空间不足" );
}

int main()
{
	int A[5]={4,5,3,3,2};
	Merge_Sort(A,5);
	for(int i=0;i<5;++i)
	{
		printf("%d ",A[i]);
	}
	return 0;
}