雅乐网

归并排序是分治思想的典型应用。它的基本步骤有3步：

1. 划分。将要排序的数组分为两部分。

2. 递归求解。分别递归使用归并排序将两部分排序。

3. 合并。将两个有序的序列合并为一个有序的序列。

将序列分为两部分用时O（1），而对子序列进行递归排序耗时2 * T(n/2)，对排好的两个序列合并用时O（n）。

由于每次减为n/2 。算法的总体复杂度为O（nlogn）

主代码mergesort

代码的主体部分如下：

思想是，排序前半部分，排序后半部分，将两部分归并为一个部分。

void merge_sort(int *a, int low, int high)
{
	int mid;
	if (high - low < 2) return; //递归基 该序列只有一个元素 是有序的
	mid = (low + high) / 2;

	merge_sort(a, low, mid);	//左半部分排序
	merge_sort(a, mid, high);	//右半部分排序

	merge(a, low, mid, high);	//合并两个排好序的序列
}

 归并两个有序序列

只需每次比较两个序列的第一个，取出较小者，再比较两个序列的第一个……

左半部分[low, mid) 右半部份[mid, high)

代码如下

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>

#define N 1000


void merge(int *_elem, int lo, int mid, int hi);
void mergesort(int *_elem, int lo, int hi);


int main(void)
{
	int i;
	int a[N];

	srand((int)time(NULL));

	for (i = 0; i < N; ++i)
	{
		a[i] = rand() % 10000;
	}

	mergesort(a, 0, N);

	for (i = 0; i < N; ++i)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}


void merge(int *_elem, int lo, int mid, int hi)
{
	int i, j, k;
	int * L = (int *)malloc(sizeof(int)*(mid-lo));	
	int lenL = mid - lo;
	//左半部分备份出来
	for (i = lo; i < mid; ++i)
		L[i-lo] = _elem[i];

	i = 0;	//左半部分指针
	j = mid;	//右半部分指针
	k = lo;	//记录结果数组下标

	while (i < lenL && j < hi)
	{
		if (L[i] <= _elem[j])
			_elem[k++] = L[i++];
		else
			_elem[k++] = _elem[j++];
	}
	
	while (i < lenL)
		_elem[k++] = L[i++];
}

void mergesort(int *_elem, int lo, int hi)
{
	if (hi - lo < 2) return;
	int mid = lo + (hi - lo) / 2;
	mergesort(_elem, lo, mid);
	mergesort(_elem, mid, hi);
	merge(_elem, lo, mid, hi);
}