You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

78 lines
2.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
/*
归并排序思路
1.把长度为n的输入序列分成两个长度为n/2的子序列
2.对这两个子序列分别采用归并排序;
3.将两个排序好的子序列合并成一个最终的排序序列。
*/
// #define与const的区别
// https://blog.csdn.net/qq_41057885/article/details/79218927
#define N 1000
//这个归并排序应该说是非常的经典,二分法用到了好处~赞~~~,但这些细节处理起来确实麻烦
void __merge(int arr[], int left, int mid, int right) {
//动态声明一个aux数据通过数组指针可以动态声明数组
int *aux = new int[right - left + 1];
// 拷贝一遍数组
for (int i = left; i <= right; i++)
aux[i - left] = arr[i];
//左指针,右指针
int i = left, j = mid + 1;
// arr数组用来排序aux数组是原来的数组序列
for (int k = left; k <= right; k++) {
if (i > mid) {
arr[k] = aux[j - left];//其实这里只有进来一次的机会即到了mid处因为下面的i++,所以这里需要判断i>mid
j++;
} // 左边已排序完成
else if (j > right) {
arr[k] = aux[i - left];//同理这里也是当右指针到了right时进来一次就是到了最后。
i++;
} // 右边已排序完成
else if (aux[i - left] < aux[j - left]) {
arr[k] = aux[i - left];
i++;
} // 左边小于右边
else { // 右边小于左边
arr[k] = aux[j - left];
j++;
}
}
//动态声明的数组指针,需要显式删除
delete[]aux;
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
// C++ 传递数组给函数(是按指针传递的就是会改变arr[]的内容)
//https://www.runoob.com/cplusplus/cpp-passing-arrays-to-functions.html
void __mergeSort(int arr[], int left, int right) {
//两边相遇到,则停止
if (left >= right)
return;
//找到中点,如果是奇数,那么正是是一半,如果是偶数,目前的算法是靠左
int mid = left + (right - left) / 2;
//递归调用,对左侧一半进行排序
__mergeSort(arr, left, mid);
//递归调用,对右侧一半进行排序
__mergeSort(arr, mid + 1, right);
//根据三个结点号进行left---mid---right的合并
__merge(arr, left, mid, right);
}
int main() {
int n;
int arr[N];
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
//归并排序
__mergeSort(arr, 0, n - 1);
//输出结果
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
}