别在这里问什么是归并排序,请善用搜索引擎,数据结构系列的学习笔记只是我用来整理,归纳和复习的系列,不会说原理。

相关代码

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
102
103
104
105
106
107
108
109
110
111
112
113
114
//
// Created by Tianyi on 2021/11/10.
//
#include <iostream>

using namespace std;


void merge_sort_c(int *arr, int start, int end);
void merge(int *arr, int start, int mid, int end);
void show(int *arr, int len);


void marge_sort(int *arr, int len) {
if (len <= 1) {
return;
}

merge_sort_c(arr, 0, len - 1);
}


void merge_sort_c(int *arr, int start, int end) {
if (start >= end) {
return;
}

int mid = (start + end) / 2;

// 切左边
merge_sort_c(arr, start, mid);
// 切右边
merge_sort_c(arr, mid + 1, end);

// 合并左右切片
merge(arr, start, mid, end);
}


void merge(int *arr, int start, int mid, int end) {
// 计算当前大切片的长度
int len = end - start + 1;
// 申请一个临时的数组用于存储大切片的正确顺序
int *tempArr = new int[len];
// 初始化大切片下标
int tempIndex = 0;

// 左切片起始位置
int leftIndex = start;
// 右切片起始位置
int rightIndex = mid + 1;

// 对两个切片进行比较,依次放入临时数组
while (leftIndex <= mid && rightIndex <= end) {
if (arr[leftIndex] >= arr[rightIndex]) {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
} else {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
}

tempIndex++;
}

// 用于临时存储剩余切片的起始位置和终止位置
int residueIndex;
int residueEnd;
// 判断是左切片没有存储还是右切片没有存储
if (leftIndex <= mid) {
residueIndex = leftIndex;
residueEnd = mid;
} else {
residueIndex = rightIndex;
residueEnd = end;
}
// 将剩余的切片存入临时数组中
while (residueIndex <= residueEnd) {
tempArr[tempIndex] = arr[residueIndex];
tempIndex++;
residueIndex++;
}

// 打印步骤
show(tempArr, len);

// 将正确的顺序覆盖到原来的数组中
for (int i = start, tempIndex = 0; i <= end; i++, tempIndex++) {
arr[i] = tempArr[tempIndex];
}

// 释放临时数组使用的内存
free(tempArr);
}


void show(int *arr, int len) {
for (int i = 0; i < len; ++i) {
cout << "(" << arr[i] << ")" << " - ";
}
cout << endl;
}


int main() {
int arr[] = {5, 3, 6, 2, 1, 4, 0, -7, -9, -3, -6, -1};

int len = sizeof(arr) / sizeof(int);

marge_sort(arr, len);
show(arr, len);

return 0;
}