排序算法总结（三）归并排序

原理：

1、把当前序列平分为两个子序列，i，j分别指向两个 序列的头部
2、递归地对子序列进行递归
3、把排序好的子序列再合并成一个有序的序列

代码：

#include <iostream>
#include <unistd.h>
#include <sys/wait.h>
#include <algorithm>
#include <string.h>

#define DEBUG ON

static void merge(int arr[], int low, int mid, int high, int tmp[])
{
	int i = low, j = mid + 1, k = 0;
	while (i <= mid && j <= high)
	{
		if (arr[i] <= arr[j])
		{
			tmp[k++] = arr[i++];
		}
		else
		{
			tmp[k++] = arr[j++];
		}
	}
	while (i <= mid) tmp[k++] = arr[i++];
	while (j <= high) tmp[k++] = arr[j++];

#ifdef DEBUG
    std::cout<<"sort: ";
	for (int v = low; v < low + k; v++)
	{
		std::cout << arr[v] << " ";
	}
	std::cout << std::endl;
#endif // DEBUG
	
	memcpy(&arr[low], tmp, k*sizeof(int));
	//debug
#ifdef DEBUG
    std::cout<<"output: ";
	for (int v = low; v < low + k; v++)
	{
		std::cout << arr[v] << " ";
	}
	std::cout << std::endl;
#endif // DEBUG
}

static void merge_sort(int arr[], int low, int high, int tmp[])
{
	if (low < high)
	{
		int mid = low + (high - low) / 2;
		merge_sort(arr, low, mid, tmp);
		merge_sort(arr, mid + 1, high, tmp);
		merge(arr, low, mid, high, tmp);
	}
}
static void sort_recursive(int arr[], int length)
{
	if (arr == nullptr || length == 0) return;
	int *tmp = new int[length];
	merge_sort(arr, 0, length - 1, tmp);

}

static void sort_iterative()
{

}

int main()
{
	int a[] = { 6,5,3,1,8,7,2,4 };
	int length = sizeof(a) / sizeof(int);
	sort_recursive(a, length);
	return 0;
}

输出效果

执行完成，耗时：0 ms
sort: 6 5 
output: 5 6 
sort: 3 1 
output: 1 3 
sort: 5 6 1 3 
output: 1 3 5 6 
sort: 8 7 
output: 7 8 
sort: 2 4 
output: 2 4 
sort: 7 8 2 4 
output: 2 4 7 8 
sort: 1 3 5 6 2 4 7 8 
output: 1 2 3 4 5 6 7 8 ```