【C++】归并排序

  归并排序主要利用了“归并”思想，对序列进行排序。归并排序的原理是：将序列两两分组，将序列归并为[n / 2]个组，组内单独排序。然后将这些组再两两归并，生成[n / 4]个组，组内再单独排序，以此类推，直到只剩下一个组为止。另外，归并排序的时间复杂度为：O(n logn) 。

下面来看看归并排序的两种简单实现。

  反复将当前区间分为两半，对两个子区间分别递归进行归并排序，最后将两子区间合并为一有序序列即可。

#include

using namespace std;

//归并排序 递归实现

const int k = 100;

void merge(int A[], int L1, int R1, int L2, int R2){//将数组A的[L1, R1]与[L2, R2]区间合并为有序区间 L2 = R1+1 
 	int i = L1,j = L2;//i指向L1，j指向L2 
 	int temp[k] , index = 0;//temp临时存放合并后的数组，index为temp数组下标 
 	while(i <= R1 && j <=R2){ 
  		if(A[i] <= A[j]){
   		temp[index++] = A[i++]; //将A[i]加入数组 
  		}else{
   			temp[index++] = A[j++];//将A[j]加入数组 
  		}
 	}
 	//分别将[L1, R1]、[L2, R2]的剩余元素加入数组 
 	while(i <= R1) temp[index++] = A[i++]; 
 	while(j <= R2) temp[index++] = A[j++];
 	for(i = 0; i < index; i++){
  		A[L1 + i] = temp[i];//将合并后的数组赋值回A 
 	}
}
//将当前数组进行归并排序 
void mergeSort(int A[], int left, int right){
 	if(left < right){
  		int mid = (left + right) / 2;//取[left, right]中点 
  		mergeSort(A, left, mid);//递归 将[left, mid]归并排序 
  		mergeSort(A, mid + 1, right);//递归 将[mid+1, right]归并排序 
  		merge(A, left, mid, mid + 1, right);//将两区间合并 
 	}
}

int main(){
 	int A[7] = {66, 12, 33, 57, 64, 27, 18};
 	mergeSort(A, 0, 6);//归并排序 
 	for(int i = 0; i <=6; i++) cout< 
非递归实现 
  令step的初值为 2，然后将数组中每step个元素作为一组，将其内部进行排序，再令step * 2，重复上面的操作，直到step / 2超过元素个数n。
 
#include

using namespace std;
//归并排序 非递归实现

const int k = 100;
void merge(int A[], int L1, int R1, int L2, int R2){//将数组A的[L1, R1]与[L2, R2]区间合并为有序区间 L2 = R1+1 
 	int i = L1,j = L2;//i指向L1，j指向L2 
 	int temp[k] , index = 0;//temp临时存放合并后的数组，index为temp数组下标 
 	while(i <= R1 && j <=R2){ 
  		if(A[i] <= A[j]){
   		temp[index++] = A[i++]; //将A[i]加入数组 
  		}else{
   			temp[index++] = A[j++];//将A[j]加入数组 
  		}
 	}
 	//分别将[L1, R1]、[L2, R2]的剩余元素加入数组 
 	while(i <= R1) temp[index++] = A[i++]; 
 	while(j <= R2) temp[index++] = A[j++];
 	for(i = 0; i < index; i++){
  		A[L1 + i] = temp[i];//将合并后的数组赋值回A 
 	}
}
void mergeSort(int A[], int n){
	//step为组内元素个数，step / 2为左区间元素个数
	for(int step = 2; step / 2 <= n; step *= 2){
		//每step个元素一组，组内前step / 2和后step / 2个元素进行合并 
		for(int i = 0; i < n; i += step){ //对每一组进行操作 
			int mid = i + step / 2 - 1;//当前组的中间元素下标 
			if(mid + 1 <= n){
				merge(A, i, mid, mid + 1, min(i + step -1, n-1));
			} 
		}
	}  
}
int main(){
 	int A[7] = {66, 12, 33, 57, 64, 27, 18};
 	mergeSort(A, 7);//归并排序 
 	for(int i = 0; i <=6; i++) cout< 
当然，也可以很快乐地使用sort方法
 
void mergeSort(int A[], int n){
	for(int step = 2; step / 2 <= n; step *= 2){
		//每step个元素一组，组内前step / 2和后step / 2个元素进行合并
		for(int i = 0; i < n; i += step){
			sort(A + i, A + min(i + step, n));
		}
		//可在此输出每一次归并排序结束的序列 
	}
}
 
附： 
如有错误欢迎各位在评论区指正