vlambda博客
学习文章列表

#include <iostream>
using namespace std;
// 合并void merge(int a[], int left, int mid, int right) { // 创建两个临时数组，分别存储数组a的left～mid（左边）和mid+1~right（右边）数据 int m = mid - left + 1, n = right - mid; int left_a[m]; int right_a[n]; for (int i = 0; i < m; i++) left_a[i] = a[left + i]; for (int i = 0; i < n; i++) right_a[i] = a[mid + 1 + i];
 // 开始合并 int i = 0, j = 0, k = left; // 左边和右边各拿一个，进行比较，小的放回数组a while (i < m && j < n) { if (left_a[i] < right_a[j]) a[k++] = left_a[i++]; else a[k++] = right_a[j++]; } // 如果左边还有，把左边的放回数组a while (i < m) a[k++] = left_a[i++]; // 如果右边还有，把左边的放回数组a while (j < n) a[k++] = right_a[j++];}
void mergeSort(int a[], int left, int right) { // 只要还可以分 if (left < right) { // 找到中间点 int mid = (left + right) / 2; // 分成两部分 mergeSort(a, left, mid); mergeSort(a, mid + 1, right); // 调用自定义函数merge进行合并 merge(a, left, mid, right); }}
int main() { int n; cin >> n; int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
 mergeSort(a, 0, n - 1);
 for (int i = 0; i < n; i++) cout << a[i] << ' ';
 return 0;}