算法：MERGESORT
伪代码如下：
输入：n个元素的数组A[1...n]
输出：按非降序排列的数组A[1...n]
mergesort(A,1,n)
mergesort(low,high)
if low<high then
mid←(low+high)/2
mergesort(A,low,mid)
mergesort(A,mid+1,high)
MERGE(A,low,mid,high)
end if
此算法时间复杂度为：Θ（nlogn）
详细代码如下：
#include <iostream>
using namespace std;
#define length 500
//合并的辅助函数
void merge(int *data, int low, int mid, int high)
{
std::cout << "merge low is" << low << " mid is:" << mid << " high is" << high << std::endl;
int newLength = high - low + 1;
int *newData = new int[newLength];
int i = low, j = mid + 1, k = 0;
//分解2个数组，并且合并完其中的一个数组
while (i <= mid && j <= high)
{
if (data[i] <= data[j])
newData[k++] = data[i++];
else
newData[k++] = data[j++];
}
//合并另外一个数组
while (i <= mid)
newData[k++] = data[i++];
while (j <= high)
newData[k++] = data[j++];
//把新数据的数组拷贝到原始数组里面去
for (int i = low, k = 0; i <= high; ++i)
{
data[i] = newData[k++];
std::cout << "data[" << i << "] is" << data[i] << "\t";
}
delete[] newData;
std::cout << std::endl;
}
//合并排序
void mergeSort(int *data, int low, int high)
{
std::cout << "mergeSort low is" << low << " high is" << high << std::endl;
if (low < high)
{
int mid = (low + high) / 2;
mergeSort(data, low, mid);
mergeSort(data, mid + 1, high);
merge(data, low, mid, high);
}
}
int main()
{
int all, data[length];
std::cout << "请输入需要排序的数据的个数" << std::endl;
std::cin >> all;
if (all <= 0)
std::cout << "输入的数据有误" << std::endl;
//input data
for (int i = 0; i < all; ++i)
{
std::cin >> data[i];
}
//分治排序
mergeSort(data, 0, all - 1);
//printf data
for (int i = 0; i < all; ++i)
{
std::cout << data[i] << "\t";
}
std::cout << std::endl;
return 0;
}
