排序-归并排序
跟着两位大佬的步伐继续学算法,这次是归并排序,还是直接上代码。。。
- http://blog.csdn.net/jofranks/article/details/7802447
- http://blog.csdn.net/morewindows/article/details/6678165/
代码
#include <iostream>
using namespace std;
void mergeArray(int* a, int first, int mid, int last, int* res) //将两个有序数列合并
{
int i = 0;
int left = first;
int right = mid + 1;
while(left <= mid && right <= last)
{
if(a[left] < a[right])
res[i++] = a[left++];
else
res[i++] = a[right++];
}
while(left <= mid)
res[i++] = a[left++];
while(right <= last)
res[i++] = a[right++];
for(int j = 0; j < i; j++) //将最终结果放到原数组里,删除临时数组res,减少new操作,节省时间
a[first+j] = res[j];
}
void mergeSort(int* a, int first, int last, int* res)
{
if(first < last)
{
int mid = (first + last) / 2;
mergeSort(a, first, mid, res); //数列左边递归分解,使其有序
mergeSort(a, mid+1, last, res); //右边
mergeArray(a, first, mid, last, res); //合并左右序列
// for(int i = 0; i < 10; i++)
// cout << a[i] << ' ';
// cout << endl;
}
}
int main()
{
int num;
cin >> num;
int* res = new int [num];
int* a = new int [num];
for(int i = 0; i < num; i++)
cin >> a[i];
mergeSort(a, 0, num-1, res);
for(int i = 0; i < num; i++)
cout << a[i] << ' ';
cout << endl;
delete [] a;
delete [] res;
return 0;
}
Wonderful material. Thanks a lot!