【算法】归并排序

归并排序

当两组数据已经有序，我们可以通过以下方式让两组数据快速排序。

依次从两组数据中取前面最小的元素放到新的数组中，然后再把新数组中有序的数据拷贝到原数组，完成排序。这就是归并思想。

代码实现

#include<iostream>
using namespace std;

void mergeAdd(int* arr,int left,int mid,int right)
{
	int temp[64] = { 0 };
	int i = left;//指向左边数组最小的元素位置
	int j = mid;//指向右边数最小的元素位置
	int k = 0;//临时数组下标

	while (i < mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while(i< mid)
	{
		temp[k++] = arr[i++];
	}
	while (j <= right)
	{
		temp[k++] = arr[j++];
	}
	//把temp中内容拷贝到
	memcpy(arr + left, temp+left, sizeof(int) * (right - left + 1));
	
}

void print(int* arr,int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}
int main(void)
{
	int arr[] = { 1,3,5,7,2,4,6,8 };
	int len = sizeof(arr) / sizeof(arr[0]);
	int mid = len / 2;
	mergeAdd(arr, 0,mid, len - 1);
	print(arr, len);
	return 0;
}

---

当数据无序的时候，只用归并思想就无法实现排序了。

---

依靠这种思想，引出归并排序方法。

下面是一组待排序的数组。

以中间为界，分为两个数组。

再进行细分

再分

利用上面的归并思想将两个数组分别有序

最后合并到一起。

代码实现(分治法+归并思想)

#include<iostream>
using namespace std;

//归并法，将两个有序的数组合并到一起
void mergeAdd(int* arr,int left,int mid,int right,int* temp)
{

	int i = left;//指向左边数组最小的元素位置
	int j = mid;//指向右边数最小的元素位置
	int k = left;//临时数组下标

	while (i < mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while(i< mid)
	{
		temp[k++] = arr[i++];
	}
	while (j <= right)
	{
		temp[k++] = arr[j++];
	}
	//排好序的存到原来的位置——分块排序时，对应位置的元素，分治归并后还放在对应的位置。
	memcpy(arr + left, temp+left, sizeof(int) * (right - left + 1));
	
}

void print(int* arr,int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

void mergeSort(int* arr,int left,int right,int* temp)
{
	int mid = 0;
	if (left < right)
	{
		mid = left + (right - left) / 2;//找中间值
		mergeSort(arr, left, mid, temp);
		mergeSort(arr, mid + 1, right, temp);
		mergeAdd(arr, left,mid+1, right, temp);//mid在整合的时候算在右边那半
	}
}
int main(void)
{
	int arr[] = { 3,1,4,5,5,4,1,3};
	int len = sizeof(arr) / sizeof(arr[0]);
	int mid = len / 2;
	int* temp = new int[len];
	mergeSort(arr, 0, len - 1, temp);
	mergeAdd(arr, 0,mid, len - 1,temp);
	print(arr, len);
	return 0;
}