- 注册时间
- 2007-5-30
- 最后登录
- 1970-1-1
- 日志
- 阅读权限
- 100
|

楼主 |
发表于 2013-5-9 11:00:12
|
显示全部楼层
并归排序
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;//6 8 7 9 -9 4 1 2
class MergeSort//并归排序
{
private:
vector<int> arr, temp;
public:
MergeSort()
{
cout<<"please input a array of integer: "<<endl;
int x;
while (cin >> x)
{
arr.push_back(x);
}
temp.resize(arr.size());
DoMergeSort(0, arr.size()-1);
print();
}
~MergeSort()
{
}
void MergeArray(int l, int m, int r)//2个有序的数组合并
{
int i = l, j = m+1, k = 0;
while (i <= m && j <= r)
{
if (arr[i] < arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
while (i<=m)
{
temp[k++] = arr[i++];
}
while (j<=r)
{
temp[k++] = arr[j++];
}
//这是个子序列,l是子序列的开始,k是子序列的长度
for (i = 0; i < k; i++)
{
arr[l + i] = temp[i];
}
}
void DoMergeSort(int l, int r)
{
if (l < r)
{
int m = (l + r) / 2;
DoMergeSort(l, m);//左边有序
DoMergeSort(m+1, r);//右边有序
MergeArray(l, m, r);//再将二个有序数列合并
}
}
void print()
{
for (int i = 0; i < arr.size(); i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
};
void main()
{
MergeSort ms;
} |
|