数据结构：归并排序

归并排序

void _MergeSort(int array[], int left, int right, int* temp)
{
	if (right - left <= 1)
		return;
	//将区间均分成两部分
	int mid = left + ((right - left) >> 1);
	//递归排左半侧[left,mid)
	_MergeSort(array, left, mid, temp);
	//递归排右半侧[mid,right)
	_MergeSort(array, mid, right, temp);
	//将 有序的左半侧 和 有序的右半侧 合并成一个
	MergeData(array, left, mid, right, temp);
	memcpy(array + left, temp + left, (right - left) * sizeof(int));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void MergeData(int array[], int left, int mid, int right, int* temp)
{
	//左半侧
	int begin1 = left;
	int end1 = mid;
	//右半侧
	int begin2 = mid;
	int end2 = right;

	int index = left;
	//将两个区间中的元素，从前往后依次比较，将较小的元素搬移至temp中
	while (begin1 < end1 && begin2 < end2)
	{
		if (array[begin1] <= array[begin2])
			temp[index++] = array[begin1++];
		else
			temp[index++] = array[begin2++];
	}
	//将另一个区间中剩余元素搬移至temp中
	while (begin1 < end1)
	{
		temp[index++] = array[begin1++];
	}
	while (begin2 < end2)
	{
		temp[index++] = array[begin2++];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include
#include
#include

void MergeData(int array[], int left, int mid, int right, int* temp)
{
	//左半侧
	int begin1 = left;
	int end1 = mid;
	//右半侧
	int begin2 = mid;
	int end2 = right;

	int index = left;
	//将两个区间中的元素，从前往后依次比较，将较小的元素搬移至temp中
	while (begin1 < end1 && begin2 < end2)
	{
		if (array[begin1] <= array[begin2])
			temp[index++] = array[begin1++];
		else
			temp[index++] = array[begin2++];
	}
	//将另一个区间中剩余元素搬移至temp中
	while (begin1 < end1)
	{
		temp[index++] = array[begin1++];
	}
	while (begin2 < end2)
	{
		temp[index++] = array[begin2++];
	}
}

void _MergeSort(int array[], int left, int right, int* temp)
{
	if (right - left <= 1)
		return;
	//将区间均分成两部分
	int mid = left + ((right - left) >> 1);
	//递归排左半侧[left,mid)
	_MergeSort(array, left, mid, temp);
	//递归排右半侧[mid,right)
	_MergeSort(array, mid, right, temp);
	//将 有序的左半侧 和 有序的右半侧 合并成一个
	MergeData(array, left, mid, right, temp);
	memcpy(array + left, temp + left, (right - left) * sizeof(int));
}

void MergeSort(int array[], int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	if (temp == NULL)
	{
		assert(0);
		return;
	}
	_MergeSort(array, 0, size, temp);
	free(temp);
}


//非递归  归并排序
void MergeSortNor(int array[], int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	if (temp == NULL)
	{
		assert(0);
		return;
	}
	int gap = 1;
	while (gap < size)
	{
		for (int i = 0; i < size; i = i + gap * 2)
		{
			//每个区间有gap个元素
			//[left,mid),[mid,right)
			int left = i;
			int mid = left + gap;
			int right = mid + gap;
			//[left,mid),[mid,right)进行归并
			MergeData(array, left, mid, right, temp);
		}
		memcpy(array, temp, sizeof(int) * size);
		gap <<= 1;
	}
	free(temp);
}


int main()
{
	int array[] = { 3,1,8,6,0,2,7,9,4,5 };
	MergeSort(array, sizeof(array) / sizeof(array[0]));
	//MergeSortNor(int array[], int size)
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", array[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

上机实践：