时间复杂度O(n*logn)
#include <iostream> using namespace std; void Merge(int a[], int s, int m, int e, int temp[]) {//将数组a的局部a[s, m]和a[m+1, e]合并到temp,并保证temp有序，再拷贝回a[s, m] int pb = 0; int p1 = s, p2 = m+1; while(p1<=m && p2<=e) { if(a[p1] < a[p2] ) temp[pb++] = a[p1++]; else temp[pb++] = a[p2++]; } while(p1<=m) temp[pb++] = a[p1++]; while(p2<=e) temp[pb++] = a[p2++]; for(int i=0; i<e-s+1; i++) a[s+i] = temp[i]; } void MergeSort(int a[], int s, int e, int temp[]) { if(s<e)//s>=e即是递归的终止条件 { int m = s + (e - s)/2; MergeSort(a, s, m, temp); MergeSort(a, m+1, e, temp); Merge(a, s, m, e, temp); } } int a[10] = {89, 72, 42, 63, 98, 17, 2, 2, 9, 90}; int b[10];//临时变量数组 int main() { int size = sizeof(a) / sizeof(int); MergeSort(a, 0, size-1, b); for(int i=0; i<size; i++) cout << a[i] << ","; cout << endl; return 0; } ReCclay 认证博客专家 嵌入式软件开发 机器/深度学习 全栈技术学习者 大家好，我是博主ReCclay，目前处于研究生阶段，就读于电子科技大学，主攻方向为汽车辅助驾驶算法研究。入站以来，凭借坚持与热爱，以博文的方式分享所学，截止目前累计博文数量达800余篇，累计受益人次达130w+次，涉及领域包括但不限于物联网开发、单片机开发、Linux驱动开发、FPGA开发、前/后端软件开发等。在未来我将继续专注于嵌入式相关领域，学习更多的科技知识，输出更高质量的博文。