归并排序

1.思路

通过不断的划分区域，使其每个区域独自有序，为后续的合并埋下伏笔。由于两个区域是有序的，合并的时候就会降低排序的时间复杂度。

2.代码

2.1递归思想

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

int n;
int* a;

void init() {
	printf("请输入n：");
	scanf("%d", &n);
	a = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
}

void print() {
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
}

void merge(int* temp, int left, int mid, int right) {
	int l_pos = left;
	int r_pos = mid + 1;
	int pos = l_pos;
	while (l_pos <= mid && r_pos <= right) {
		if (a[l_pos] < a[r_pos])
			temp[pos++] = a[l_pos++];
		else
			temp[pos++] = a[r_pos++];
	}
	while (l_pos <= mid)
		temp[pos++] = a[l_pos++];
	while(r_pos <= right)
		temp[pos++] = a[r_pos++];
	while (left <= right) {
		a[left] = temp[left];
		left++;
	}
}

void Sort(int* temp, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		Sort(temp,left,mid);
		Sort(temp, mid + 1, right);
		merge(temp,left,mid,right);
	}
}

void mergeSort() {
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp) {
		Sort(temp, 0, n - 1);
		free(temp);
	}
	else
		printf("error:failed to allocate the memory");
}

int main() {
	init();
	mergeSort();
	print();
	free(a);
	return 0;
}

2.2迭代思想

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

int n;
int* a;

void init() {
	printf("请输入n：");
	scanf("%d", &n);
	a = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
}

void print() {
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
}

void merge(int* temp, int left, int mid, int right) {
	int l_pos = left;
	int r_pos = mid + 1;
	int pos = l_pos;
	while (l_pos <= mid && r_pos <= right) {
		if (a[l_pos] < a[r_pos])
			temp[pos++] = a[l_pos++];
		else
			temp[pos++] = a[r_pos++];
	}
	while (l_pos <= mid)
		temp[pos++] = a[l_pos++];
	while(r_pos <= right)
		temp[pos++] = a[r_pos++];
	while (left <= right) {
		a[left] = temp[left];
		left++;
	}
}

void Sort(int* temp, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		Sort(temp,left,mid);
		Sort(temp, mid + 1, right);
		merge(temp,left,mid,right);
	}
}

void mergeSort() {
	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp) {
		Sort(temp, 0, n - 1);
		free(temp);
	}
	else
		printf("error:failed to allocate the memory");
}

int main() {
	init();
	mergeSort();
	print();
	free(a);
	return 0;
}