|
|
#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] << " ";
|
|
|
}
|
|
|
} |