merge_sort

[c++]代码库

#include<iostream>
using namespace std;
#define size 6

//合并函数 
void merge(int array[],int first,int mid,int last){
	
	int temp[size]; //声明一个临时数组temp
	int i; //控制变量i
	int j = first; //控制变量j，初始值为最小数组下标first，first-mid为左半数组 
	int n = mid+1; //控制变量n，初始值为数组中间下标mid，+1，mid+1到last为右半数组
	int k = first; //控制变量k，初始值为最小数组下标0，控制临时数组temp的下标 
	
	//将临时数组temp的每一个值初始化为 0 
	for(i=0;i<size;i++){
		
		temp[i]=0;
	}
	//将控制变量 i 置零，以便后面继续使用 
	i = 0;
	
	
	// 当左半数组和右半数组都不为空时... 
	while(j<=mid&&n<=last){
		
		if(array[j]<array[n]){
			
			temp[k] = array[j];
			k++;j++;
		
		}
		else{
			temp[k] = array[n];
			k++;n++;
		}
	}
	
	//当右数组为空时，输出另一数组的剩余元素 
	while(j<=mid&&n>last){
		temp[k] = array[j];
		k++;j++;
	}
	
	//当左数组为空时，输出另一数组的剩余元素 
	while(n<=last&&j>mid){
		temp[k] = array[n];
		k++;n++;
	}

	//将temp数组赋值给原数组
	for(i=first;i<=last;i++){
		array[i] = temp[i];
	}
} 



//排序函数 
void sort(int array[], int first, int last){
	
	
	if(first<last){
		
		int mid = (first+last)/2;
		sort(array,first,mid);//递归排序左数组 
		sort(array,mid+1,last);//递归排序右数组 
		merge(array,first,mid,last);//调用merge函数，合并 
	}
}



int main(){
	
	int array[size] = {3,342,112,43,446,318};
	sort(array,0,size-1);
	for(int i=0;i<size;i++){
		cout<<array[i]<<" ";
	}
	return 0; 
}