1. 归并排序（排序的方法一种，速度比选择排序、插入排序等快很多）适合较多数据排序
2. 归并排序思想（拆分、合并）
2.1 拆分
image
2.2 合并
image
2.2 合并详解
image
#include<iostream>
using namespace std;
int a[100] = { 5,33,3,7,11,6,8,100 };
/*
创一个辅助空间，合并两个有序的数组
*/
void Merge(int a[],int start,int mid,int end) {
int result[100];
int k = 0;
int i = start, j = mid + 1;
while (i <= mid && j <= end) { //合并两个有序的数组，谁小先放到result数组中
if (a[i] < a[j])
result[k++] = a[i++];
else
result[k++] = a[j++];
}
if (i == mid + 1) { //处理剩下的未合并的数组元素
while (j <= end)
result[k++] = a[j++];
}
if (j == end + 1) {//处理剩下的未合并的数组元素
while (i <= mid)
result[k++] = a[i++];
}
for (k = 0,start; start <= end; start++,k++) { //把result结果复制回待排序的数组中
a[start] = result[k];
}
}
void mergeSort(int a[],int start,int end) {
if (start >= end) return;
int mid = (start + end) / 2;
mergeSort(a,start,mid);
mergeSort(a, mid + 1, end);
Merge(a,start,mid,end);
}
int main() {
int len = 8;
mergeSort(a, 0, len - 1);
for (int i = 0; i < len; i++) cout << a[i] << " ";
return 0;
}
