归并排序C语言

归并排序

  所谓 “归并” 就是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并就是直接将两个有序的子表合并成一个有序的表。这种反复将两个有序子表归并成一个有序表的排序方法称为两路归并排序，其核心操作是将一维数组中前后相邻的两个有序序列合并为一个有序序列。

算法描述

假设：对于数组 N【n】进行归并排序
两两归并排序：执行两两归并操作，将两个有序子表 data[s…m] 和 data[m+1…n] 归并为一个有序的表 data[s…n]
每趟归并的子表长度：对于长度为 n 的数表，从长度为 length = 1 的子表开始两两归并，每次
长度 x 2，即 length *= 2，直到 length <= n - 1
长度为len的子表进行两两归并：子表从位置 i 开始，当子表长度为len时，两个子表分别为 N[i … i+len-1] 和 N[i+len … i+2*len-1]，子表开始位置每次增加两倍的表长，即 len = i + 2 * len，直到整个数表末尾，
即 i + 2 * len - 1 < n
边界条件：当 i + 2 *len - 1 >= n 时，结束归并排序，但此时可能存在元素 N[i+len … n-1] 没有归并到数表
因此当 i + len - 1 < n 时，继续两两归并子表 N[i … i+len-1] 和 N[i+len … n-1]

---

代码实现

// 执行两两归并
void MergeDouble(int *N, int start, int mid, int end)
{
	int *tmp_N = (int *)malloc(sizeof(int) * (end - start + 1));  // 申请临时内存
	if(tmp_N == NULL)
		return;
	int i, j, k;
	i = start;
	k = 0;
	for(j = mid + 1; i <= mid && j <= end; k++) {
		if(N[i] <= N[j]) {
			tmp_N[k] = N[i];
			i++;
		} else {
			tmp_N[k] = N[j];
			j++;
		}
	}
	while(i <= mid) {
		tmp_N[k++] = N[i++];
	}
	while(j <= end) {
		tmp_N[k++] = N[j++];
	}
	// 完成归并，拷贝数据，释放内存
	k = 0;
	for(i = start; i <= end; i++) {
		N[i] = tmp_N[k++];
	}
	free(tmp_N);
}

void merge_len(int *N, int length, int n)
{
	int i;
	int len = length; // 1 2 4 8
	for(i = 0; i + 2 * len - 1 < n; i = i + 2 * len) {
		MergeDouble(N, i, i + len -1, i + 2 * len - 1);
	}
	if(i + len - 1 < n) {
		MergeDouble(N, i, i + len - 1, n - 1);
	}		
}

void mergeSort(int *N, int n)
{
	int length;
	for(length = 1; length < n; length *= 2) {
		merge_len(N, length, n);
	}
}

算法复杂度

• 时间复杂度：每一趟归并排序的时间复杂度为 O(n)，总共需进行 log2n 趟，因此时间复杂度为 O(nlog2n)
• 空间复杂度：O(n)