数据结构-归并排序（C语言）

归并排序是一个对数据比较大的一种比较快的算法，采用的是分治算法。

归并排序的原理

1、先将数据分开排序，然后再将数据合并起来。
采用一分二，二分四，四分八…的操作

2、合并排序好的序列
方法：两个序列中的数相互比较，将较小的数先插入新的序列中。

合并方法的实现函数：

void Merge(int array[], int left, int mid, int right, int *extra) {
	int size = right - left;

	int left_index = left;
	int right_index = mid;
	int extra_index = 0;

	while (left_index < mid && right_index < right) {
		if (array[left_index] <= array[right_index]) {
			extra[extra_index] = array[left_index];
			left_index++;
		}
		else {
			extra[extra_index] = array[right_index];
			right_index++;
		}
		extra_index++;
	}

	while (left_index < mid) {
		extra[extra_index++] = array[left_index++];
	}

	while (right_index < right) {
		extra[extra_index++] = array[right_index++];
	}

	for (int i = 0; i < size; i++) {
		array[left + i] = extra[i];
	}
}

全部实现代码如下：
// 时间复杂度
// 最好 | 平均 | 最坏 O(n * log(n))
// 空间复杂度 O(n)
// 稳定性: 稳定
// 外部排序（可以对硬盘的数据进行归并）

// 合并两个有序数组
// array[left, mid)
// array[mid, right)
// 时间复杂度 O(n)
// 空间复杂度 O(n)

#include<stdio.h>
#include<malloc.c>
#include<stdlib.h>
#include<assert.c>
void Merge(int array[], int left, int mid, int right, int *extra) {
	int size = right - left;

	int left_index = left;
	int right_index = mid;
	int extra_index = 0;

	while (left_index < mid && right_index < right) {
		if (array[left_index] <= array[right_index]) {
			extra[extra_index] = array[left_index];
			left_index++;
		}
		else {
			extra[extra_index] = array[right_index];
			right_index++;
		}
		extra_index++;
	}

	while (left_index < mid) {
		extra[extra_index++] = array[left_index++];
	}

	while (right_index < right) {
		extra[extra_index++] = array[right_index++];
	}

	for (int i = 0; i < size; i++) {
		array[left + i] = extra[i];
	}
}

// 区间是 array[left, right)
// 左闭右开的区间
void __MergeSort(int array[], int left, int right, int *extra) {
	if (right == left + 1) {
		// 区间内还剩一个数
		// 有序
		return;
	}

	if (left >= right) {
		// 区间内没有数
		return;
	}

	int mid = left + (right - left) / 2;
	// 区间被分成左右两个小区间
	// [left, mid)
	// [mid, right)
	// 先把左右两个小区间进行排序，分治算法，递归解决
	__MergeSort(array, left, mid, extra);
	__MergeSort(array, mid, right, extra);

	// 左右两个小区间已经有序了
	// 合并两个有序数组
	Merge(array, left, mid, right, extra);
}

void MergeSort(int array[], int size) {
	int *extra = (int *)malloc(sizeof(int)* size);
	assert(extra);
	memset(extra,"0",sizeof(int)*size);
	__MergeSort(array, 0, size, extra);
	free(extra);
}
int main(){
	int* array[] = { 12, 10, 6, 7, 9, 8, 5, 4, 3, 2, 1 };
	int sz = sizeof(array) / sizeof(array[0]);
	MergeSort(array, sz);
	for (int i = 0; i < sz; i++){
		printf("%d ", array[i]);
	}
	printf("\n");

	system("pause");
	return 0;
}

展现结果如下：