归并排序(带注释 )

带注释 归并排序

递归版 分而治之

void fun1(int* arr, int len);
void fun2(int* arr,int *tmp, int left,int right);
void main()
{
	int arr[] = { 14,13,12,11,10,9,8,7,6,5,4,3,2,1,0 },len=13;
	merge_sort2(len);
	cout << "\n\t--------------\n\n";
	fun1(arr, len);
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << "\t";
	}cout << endl;

}
// 使用此函数
void fun1(int *arr,int len)
{
	int* tmp = (int*)malloc(len * sizeof(int));
	fun2(arr,tmp, 0, len);
	free(tmp);

	return;
}
//包左不包右
void fun2(int* arr, int* tmp, int left, int right)
{
	// left  ---  middle  --- right
	// p1   --->  | p2 ---> right |
	// p_tmp      ---->			  |
	// 
	// 
	//递归至一个数直接返回
	if (left == right-1) return;
	//middle 中位数 
	int middle = left+((right - left) / 2 + (right - left) % 2);
	//序列有3个或以上
	if (right - left - 2 > 0)
	{
		fun2(arr, tmp, left, middle);
		//序列大于3时才向右递归
		if (right - left - 3 > 0)
			fun2(arr, tmp, middle, right);
	}

	//p1左比较点    p2 右比较点
	int p1 = left, p2 = middle,p_tmp=left;
	while (p1<middle && p2<right)
		tmp[p_tmp++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	//当左侧/右侧比较完 另一侧有剩余时
	while (p1 < middle)
		tmp[p_tmp++] = arr[p1++];
	while (p2 < right)
		tmp[p_tmp++] = arr[p2++];

	//放回arr
	for (int i = left; i < right; i++)
		arr[i] = tmp[i];

	return;
}
           

非递归 自下而上

int min(int x, int y) {
	return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
	//a 为arr指针
	int* a = arr;
	//b 为arr临时内存，用于合并两段序列
	int* b = (int*)malloc(len * sizeof(int));

	int seg, start;
	//seg 层数 seg*2 将排序序列大小
	for (seg = 1; seg < len; seg += seg) {
		//start 将排序序列开头
		for (start = 0; start < len; start += seg * 2) {
			//	low 第一组开头 mid 第二组开头 mid 第一组结尾 high为第二组结尾
			int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
			int k = low;
			// end 结尾
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			//放入 临时数组 当两序列未结束时
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			//如果一组序列有剩余
			while (start1 < end1)
				b[k++] = a[start1++];
			while (start2 < end2)
				b[k++] = a[start2++];
		}
		int* temp = a;
		a = b;
		b = temp;
	}
	//从临时数组还原
	if (a != arr)
	{
		int i;
		for (i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	free(b);
}