分治法合并排序（C++）

参考网址：http://www.cnblogs.com/Amrirey/p/5440788.html
http://blog.csdn.net/left_la/article/details/8656953

#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;
// 合并函数
void merge(int *arr, int p, int q, int r)
{
int len1 = q - p + 1;
int len2 = r - q;
int *L = new int[len1 + 1];//用动态数组储存左边的数 
int *R = new int[len2 + 1];//用动态数组储存右边的数 
for (int i = 0; i < len1; i++) {// 把Array数组左边的数放入L数组 
L[i] = arr[p + i];
}
for (int j = 0; j < len2; j++) {// 把Array数组右边的数放入R数组 
R[j] = arr[q + 1 + j];
}
L[len1]=R[len2]=INT_MAX;
//定义无穷大 
int i = 0, j = 0;
for (int k = p; k <= r; k++) {
if (L[i] < R[j]) {//小的放左边，大的放右边 
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
}
}
// 归并排序
void mergeSort(int arr[], int p, int r)
{
if (p < r)
{
int q = 0;
q = (r + p) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q+1, r);
merge(arr, p, q, r);
}
}
int main()
{
int n;
cout << "输入产生数组的个数:";
cin >> n;
cout << endl;
int *arr = new int[n];
cout << "产生的随机数组为:";
srand((unsigned)time(0));
for (int i = 0; i < n; i++)
{
arr[i] = (rand()%(100-0+1))+0;
cout << arr[i] << " ";
}
cout << endl;
mergeSort(arr,0,n-1);
cout << "排序后的数组为：";
for(int j
= 0;j<n;j++){
cout<<arr[j]<<"
";
}
system("pause");
}

最差时间复杂度：O(nlogn)
平均时间复杂度：O(nlogn)
最差空间复杂度：O(n)
稳定性：稳定

最后

以上就是眯眯眼奇迹为你收集整理的分治法合并排序（C++）的全部内容，希望文章能够帮你解决分治法合并排序（C++）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。