78 lines
2.7 KiB
C++
78 lines
2.7 KiB
C++
#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] << " ";
|
||
}
|
||
} |