归并排序
阿秀自己刷过的算法部分经过整理后是按照不同基础、不同人群分类的,如果你不知道自己该看哪个部分的算法题,可以先看一下这里,戳我直达。
# 归并排序
将一个大的无序数组有序,我们可以把大的数组分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的,所以在合并的时候是很快的。
通过递归的方式将大的数组一直分割,直到数组的大小为 1,此时只有一个元素,那么该数组就是有序的了,之后再把两个数组大小为1的合并成一个大小为2的,再把两个大小为2的合并成4的 … 直到全部小的数组合并起来。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
第二个演示动图
算法思想
1、把长度为n的输入序列分成两个长度为n/2的子序列;
2、对这两个子序列分别采用归并排序;
3、 将两个排序好的子序列合并成一个最终的排序序列。
# 1、 归并排序(C++-迭代版)
template<typename T>
void merge_sort(T arr[], int len) {
T* a = arr;
T* b = new T[len];
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
cout << low << " " << mid << " " << high << endl;
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
swap(a, b); //交换a b 地址
//T* temp = a;
// a = b;
// b = temp;
}
//if (a != arr) {
// for (int i = 0; i < len; i++)
// b[i] = a[i];
// b = a;
//}
/*
十分严谨的一种安排
每次排序都要交换 a、b 值(数组首地址)
1、if(a != arr):如果排序结束后,a 值为原来数组 b 首地址,此时 arr 与 b 相同,arr 数组内容不是最终的结果,
2、循环内容:把 a数组内容复制到数组 b(数组arr)
3、b = a :循环结束后,让 b 指向它原来的数组首地址,以便 delete[]
*/
delete[] b;
}
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
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
# 2、归并排序(C++-递归版)
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
// merge_sort
template<typename T>
void merge_sort(T arr[], const int len) {
T reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
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
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
# 3、vector 类型的递归 ,就记这一种
void mergeSortCore(vector<int>& data, vector<int>& dataTemp, int low, int high) {
if (low >= high) return;
int len = high - low, mid = low + len / 2;
int start1 = low, end1 = mid, start2 = mid + 1, end2 = high;
mergeSortCore(data, dataTemp, start1, end1);
mergeSortCore(data, dataTemp, start2, end2);
int index = low;
while (start1 <= end1 && start2 <= end2) {
dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];
}
while (start1 <= end1) {
dataTemp[index++] = data[start1++];
}
while (start2 <= end2) {
dataTemp[index++] = data[start2++];
}
for (index = low; index <= high; ++index) {
data[index] = dataTemp[index];
}
}
void mergeSort(vector<int>& data) {
int len = data.size();
vector<int> dataTemp(len, 0);
mergeSortCore(data, dataTemp, 0, len - 1);
}
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
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
节约时间的一种递归归并排序,很好,也记这一种:
void mergeSortCore(vector<int>& nums, vector<int>& copy, int begin, int end) {
if (begin >= end) return;
int mid = begin + (end - begin) / 2;
int low1 = begin, high1 = mid, low2 = mid + 1, high2 = end;
mergeSortCore(copy, nums, low1, high1);//这里减少了copy向nums的赋值部分,千万注意不要把copy 和 nums赋值反了
mergeSortCore(copy, nums, low2, high2);
int copyIndex = low1;
while (low1 <= high1 && low2 <= high2) {
copy[copyIndex++] = nums[low1] < nums[low2] ? nums[low1++] : nums[low2++];
}
while (low1 <= high1) {
copy[copyIndex++] = nums[low1++];
}
while (low2 <= high2) {
copy[copyIndex++] = nums[low2++];
}
cout << begin << " " << end << endl;
for (auto a : copy) {
cout << a << " ";
}
cout << endl;
}
void mergeSort(vector<int> nums) {
for (auto a : nums) {
cout << a << " ";
}
cout << endl;
vector<int> copyNums(nums);//这里要借助一个一模一样的数组的
mergeSortCore(nums, copyNums, 0, nums.size() - 1);
nums.assign(copyNums.begin(), copyNums.end());//到最后copy数组是排序好的,记得要赋值一下
for (auto a : nums) {
cout << a << " ";
}
}
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
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
复写
void print(vector<int>& nums) {
for (auto a : nums)
cout << a << " ";
cout << endl;
}
void mergeSort(vector<int>& data, vector<int>&temp,int begin,int end) {
if (begin >= end) return;
int low1 = begin, high2 = end, mid = begin + (end - begin) / 2;
int high1 = mid, low2 = mid + 1;
print(data);
mergeSort(temp, data, low1, high1);
mergeSort(temp, data, low2, high2);
int index = low1;
while (low1 <= high1 && low2 <= high2) {
temp[index++] = data[low1] < data[low2] ? data[low1++] : data[low2++];
}
while (low1 <= high1) {
temp[index++] = data[low1++];
}
while (low2 <= high2) {
temp[index++] = data[low2++];
}
}
void main(){
vector<int> nums = { 5,3,5,6,1,4,9,10,6,2};
vector<int> temp(nums);
mergeSort(nums,temp , 0, nums.size() - 1);
nums.assign(temp.begin(),temp.end());
}
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
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
# 4、vector 类型的迭代
void mergeSort(vector<int>& data) {
int len = data.size();
vector<int> dataTemp(len, 0);
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int index = low, start1 = low, end1 = mid, start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2) {
dataTemp[index++] = data[start1] < data[start2] ? data[start1++] : data[start2++];
}
while (start1 < end1) {
dataTemp[index++] = data[start1++];
}
while (start2 < end2) {
dataTemp[index++] = data[start2++];
}
}
swap(data, dataTemp);
}
for (auto a : data)
cout << a << " ";
}
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
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