算法导论学习之归并排序-蒲公英云

算法导论学习之归并排序

惭愧，又好久没看《算法导论》了。上次看《算法导论》的归并排序算法，后来自己写了段代码，实现了算法，不过有问题，一直也没找出问题来。今天趁着礼拜天有时间，调试一下代码。时间不早了，明天还得上班，有时间我会给代码加段注释，以及我在写这段代码的时候，遇到的问题与大家分享，防止大家也犯类似的错误。

// mergeSort.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "iostream"
using namespace std;
void printArray(int a[], int beg, int end) {
    for (int i = beg; i < end+1; i++) {
        cout << a[i] << "  ";
    }
    cout << endl;
}
void merge(int a[], int left, int middle, int right) {
    int leftLen = middle - left + 1;
    int rightLen = right - middle;
    int* tempLeft = new int[leftLen+1];
    int* tempRight = new int[rightLen+1];
    for (int i = 0; i < leftLen; i++) {
        tempLeft[i] = a[left + i];
    }
    for (int j = 0; j < rightLen; j++) {
        tempRight[j] = a[j+left+leftLen];
    }
    tempLeft[leftLen] = 100000;
    tempRight[rightLen] = 100000;
    int i = 0;
    int j = 0;
    for (int k = left; k < right+1; k++) {
        if (tempLeft[i] < tempRight[j]) {
            a[k] = tempLeft[i];
            i++;
        } else {
            a[k] = tempRight[j];
            j++;
        }    
    }
}
void mergeSort(int a[], int left, int right) {
    int middle = (left+right)/2;
    if (left < right) {
        mergeSort(a, left, middle);
        mergeSort(a, middle+1, right);
        cout << "before merge:" << endl;
        printArray(a, left, right);
        merge(a, left, middle, right);
        cout << "merged:" << endl;
        printArray(a, left, right);        
    } 
}
void test1() {
    int a[10] = {7, 6, 5, 9, 0, 3, 1, 2, 8, 4};
    mergeSort(a, 0, 9);
    cout << "final sort:" << endl;
    for (int i = 0; i < 10; i++) {
        cout << a[i] << "  ";
    }
}
int _tmain(int argc, _TCHAR* argv[])                        
{
    test1();
    int b;
    cin >> b;
    return 0;
}