归并排序算法： 思路，设置left,mid,right三个参数，对mid的左和右分别再进行递归调用归并排序算法，直到每个数组中只有1时返回，最终完成归并排序，具体思路见程序 注：归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n+logn)。 代码实现：
//归并排序（排序后为从小到大） #include <iostream> #include <algorithm> using namespace std; void Merge(int *data, int left, int mid, int right){ int *temp = new int[right - left + 1];//new一个temp保存归并后的数据 int ind = 0, i = left, j = mid + 1; while (i <= mid&&j <= right){//将两个待归并的数据进行比较存入，注意边界值 temp[ind++] = (data[i] < data[j]) ? data[i++] : data[j++]; } while (i <= mid){//将一个数组中剩余的数据存入 temp[ind++] = data[i++]; } while (j <= right){ temp[ind++] = data[j++]; } for (int i = left; i <= right; ++i){//将temp中的数据放到data里 data[i] = temp[i - left]; } delete[] temp; } void MSort(int *data, int left, int right){//递归实现归并排序 if (left >= right) return; else{ int mid = left + (right - left) / 2; MSort(data, left, mid);//分别对左右进行归并排序 MSort(data, mid + 1, right); Merge(data, left, mid, right); } } int main(){ int a[] = { 9, 1, 5, 8, 3, 7, 4, 6, 2 }; cout << "before sorted:" << endl; for (size_t i = 0; i < 9; ++i){//输出 cout << a[i] << " "; } cout << endl; int a_size = sizeof(a) / sizeof(a[0]); int *p = a; MSort(p,0,a_size-1); cout << "after sorted:" << endl; for (size_t i = 0; i < 9; ++i){//输出 cout << p[i] << " "; } cout << endl; return 0; }程序输出：
