C++实现归并排序的实例代码

写这个算法很简单，原理也很简单，但是陷阱在与这个算法中对数组的使用，下标的访问和控制。一般归并排序都是用1作下标，但是今天作死想用0作下标。恩~一直没有转过脑筋来，但是最终还是实现了。

源代码如下：

#include
#include
#include
using namespace std;
const int N = 204800;
 
void Merge(int arr[], int p, int q, int r){
    int n1 = q - p + 1;
    int n2 = r - q + 1;
    int left[n1 + 1], right[n2];
 
    for (int i = 0; i != n1; ++i){
        left[i] = arr[p + i];
    }
    left[n1] = N;
 
    for (int j = 0; j != n2 - 1; ++j){
        right[j] = arr[q + j + 1];
    }
    right[n2 - 1] = N;
 
    int i = 0, j = 0;
    for(int k = p; k != r + 1; ++k){
        if(left[i] > right[j]){
            arr[k] = right[j];
            ++j;
        }
        else{
            arr[k] = left[i];
            ++i;
        }
    }
}
 
void MergeSort(int arr[], int p, int r){
    if(p < r){
        int q = (p + r)/2;
        MergeSort(arr, p, q);
        MergeSort(arr, q + 1, r);
        Merge(arr, p, q, r);
    }
}
 
int main(){
    int arr[10] = {300, 60, 22, 16, 85, 89, 30, 99, 103, 55};
    MergeSort(arr, 0, 9);
    for(int i = 0; i < 10; ++i){
        cout<

开始的ctime本来打算用时间做种子出随机数。但是这个随机数和正态分布略符合，弃之。随机数部分代码如下：

srand(time(NULL));
int arr[rand()%100];
for (int i = 0; i != sizeof(arr)/sizeof(int); ++i){
    arr[i] = rand()%500;
}
for (int i = 0; i != sizeof(arr)/sizeof(int); ++i){
    cout<
C++ 归并排序实现（算法导论）

基本思想：设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。

#include   
using namespace std;  
void merge(int *data, int p, int q, int r)  
{  
    int n1, n2, i, j, k;  
    int *left=NULL, *right=NULL;  
   
    n1 = q-p+1;   
    n2 = r-q;  
   
    left = (int *)malloc(sizeof(int)*(n1));   
    right = (int *)malloc(sizeof(int)*(n2));  
    for(i=0; i>n;  
    input = (int *)malloc(sizeof(int)*(n));  
    cout<<"请对数组赋值: ";      
    for(int i=0; i>input[i];        
    }      
    //处理数据      
    mergeSort(input,0,n-1);      
    //输出结果      
    for(int i=0; i