归并排序

Lthero

参考《数据结构与算法c++》书中的归并算法部分
已经测试可用，10万个常数排序，速度非常快。

[C++] 纯文本查看 复制代码

#include<iostream>
#include<algorithm>
using namespace std;

void Merge(int *arr, int *temp_array, int left_begin, int right_begin, int right) {
	//point是开始对temp_数组调整的下标
	int point = left_begin;
	//左数组结束下标
	int left_end = right_begin - 1;
	//两个数组的总个数
	int num = right - left_begin + 1;
	//两个数组同向右遍历，依次找最小值
	while (left_begin <= left_end && right_begin <= right) {
		//如果左边数组的当前值更小，当前值填入temp_rray中 对应位置中
		if (arr[left_begin] < arr[right_begin]) {
			temp_array[point++] = arr[left_begin++];
		}//反之
		else {
			temp_array[point++] = arr[right_begin++];
		}
	}
	//把左数组剩下的填入temp中
	while (left_begin<=left_end)
	{
		temp_array[point++] = arr[left_begin++];
	}//右数组剩下的
	while (right_begin <= right)
	{
		temp_array[point++] = arr[right_begin++];
	}//把temp数组中，本轮调整位置的几个数字填回到原数组arr中
	//这里循环次数为 right-left+1 次 
	for (int i = 0; i < num; i++,right--) {
		arr[right] = temp_array[right];
	}
}
void Msort(int *arr, int *temp_array, int left, int right) {
	//当传入的数组个数大于1时
	if (left < right){
		//对半分割数组，如果传入5个值，left=0,right=4,center就是2 左边就是下标0~2，右边下标3~4
		int center = (right + left) / 2;
		//对左边数组继续分割
		Msort(arr, temp_array, left, center);
		//对右边数组继续分割
		Msort(arr, temp_array,  center+1,right);
		//merge是合并，将两个左右数组按顺序合并  传入，左边数组起点，右边数组起点，右边数组终点
		Merge(arr, temp_array, left,center+1, right);
	}
}
void MergeSort(int *arr, int N) {
	//构造临时数组，用于调整数字位置
	int* temp_array = new int[N];
	for (int i = 0; i < N; i++) {
		temp_array[i] = 0;
	}
	Msort(arr, temp_array, 0, N - 1);
	free(temp_array);
}
int main() {

	int size;
	//输入数组大小
	cin >> size;
	//动态分配数组
	int* arr = new int[size];
	for (int i = 0; i < size; i++) {
		cin >> arr[i];
	}
	//主代码
	MergeSort(arr, size);
	//输出
	for (int i = 0; i < size; i++) {
		cout << arr[i] << " ";
	}
	free(arr);
	cout << endl;
}