归并排序源代码:
#include <iostream>
#include <ctime>
using namespace std;
void Merge(int array[], int p, int q, int r)
{
int* temp = new int [r-p+1];
//申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
int m=p;
int n=q+1;
int k = 0;
while((m<=q)&&( n<=r))
//比较两个下标所指向的元素,选择相对小的元素放入到合并空间,并移动下标到下一位置
{
if(array[m]<array[n])
{
temp[k] = array[m];
m++;
}
else
{
temp[k] = array[n];
n++;
}
k++;
}
while(m<=q) //若第一个序列有剩余,直接拷贝出来粘到合并序列尾
{
temp[k] = array[m];
k++;
m++;
}
while(n<=r) //若第二个序列有剩余,直接拷贝出来粘到合并序列尾
{
temp[k] = array[n];
k++;
n++;
}
for (int i = 0; i < (r - p +1); i++) //将排序好的序列拷贝回数组中
{
array[p+i] = temp[i];
}
}