《算法三》（归并排序）

Whgy 2020-02-08 原文

《算法三》（归并排序）

分治思想：分而治之
归并排序：递归的拆分+合并
　　合并：两个有序数组合并为一个有序数组
　　1.准备临时数组
　　2.将数据元素依序放到临时数组中
　　3.将数据元素从临时数组拷贝回到原数组中，释放临时数组

代码演示：

#include<iostream>
#include<vector>
#include<string.h>
#define NUM 10

void print_art(int* a, int len){
	for(int i=0; i<len; i++){
		printf("%d ", a[i]);
	}
	printf("\n");
} 

//合并函数
//有序数组1：L~M  有序数组2：M+1~R 
void merge_sort(int* a, int L, int M, int R){
	//合并函数三步走：
	//1.准备临时数组
	//2.将数据元素依序放到临时数组中
	//3.将数据元素从临时数组拷贝回到原数组中，释放临时数组
	
	int len = R - L + 1;//临时数组大小 
	int* temp = new int[len];//临时数组
	int k = 0;//临时数组下标 
	int left = L;//数组1起始位置下标 
	int right = M+1;//数组2起始位置下标  
	
	while(left<=M && right<=R){
		if(a[left] < a[right]){
			temp[k++] = a[left++];
		}else{
			temp[k++] = a[right++];
		}
	}
	while(left<=M){//如果数组1还有剩余 
		temp[k++] = a[left++];
	}
	while(right<=R){//如果数组2还有剩余 
		temp[k++] = a[right++];
	}
	
	//重点：memcpy时候应该放a+L位置 
	memcpy(a+L, temp, sizeof(int)*len);
	
	delete[] temp;
	temp = NULL;
}
	  
//归并排序 
void mergesort(int* a, int L, int R){
	if( L==R ) return ;
	int m = L + (R - L ) / 2;
	mergesort(a, L, m);//拆分左边 
	mergesort(a, m+1, R);//拆分右边 
	merge_sort(a, L, m, R);//左右两边合并 
} 
	  
	  
int main(){
	int a[NUM] = {1, 3, 5, 7, 9, 0, 2, 4, 6, 8};
	mergesort(a, 0, 9);
	merge_sort(a, 0, 4, 9); 
	print_art(a, NUM);
	return 0;
}