排序算法（二） - 归并排序

归并排序的三个步骤：
一、分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
二、解决这些子问题，递归地求解各个子问题。然而，当子问题规模足够小，则直接求解。
三、合并这些子问题的解成原问题的解。

实现方法分解：
一、分解待排序的n个元素的序列成各具有n/2个元素的子序列。
二、使用归并排序递归的排序两个子序列。
三、合并两个已经排序的子序列以产生已排序的答案。

C++实现代码：

#include <iostream>
using namespace std;

/*
 归并过程
 */
void merge(int arr[], int min, int middle, int max) {
    int length1 = middle - min + 1;
    int length2 = max - middle;
    int arrA[length1], arrB[length2];

    // 将两部分用两个数组存储起来
    for (int i = 0; i < length1; i++) {
        arrA[i] = arr[min + i];
    }
    for (int i = 0; i < length2; i++) {
        arrB[i] = arr[middle + i + 1];
    }
    // 从两个数组一个一个取数据，比较大小，然后放入到arr中
    int i = 0, j = 0;
    for (int k = min; k <= max; k++) {
        if (i == length1) {         // 数组1已经全部取完，这个时候只取数组2的内容
            arr[k] = arrB[j];
            j++;
        } else if (j == length2) {  // 数组2已经全部取完，这个时候只取数组1的内容
            arr[k] = arrA[i];
            i++;
        } else if (arrA[i] <= arrB[j]) {
            arr[k] = arrA[i];
            i++;
        } else {
            arr[k] = arrB[j];
            j++;
        }
    }
}

/*
 归并排序
 */
void mergeSort(int arr[], int min, int max) {
    if (min < max) {
        int middle = int((min + max) / 2);
        mergeSort(arr, min, middle);
        mergeSort(arr, middle + 1, max);
        merge(arr, min, middle, max);
    }
}

int main(int argc, const char * argv[]) {
    int arrA[10] = {12,321,42,53,562,11,4,45,63,543};
    int arrB[15] = {23,124,5332,11,34,123,142,43,829,678,29,556,36,96,695};

    mergeSort(arrA, 0, 9);
    mergeSort(arrB, 0, 14);

    for (int i = 0; i < 10; i++) {
        cout<< arrA[i] << " ";
    }
    cout<< endl;
    for (int i = 0; i < 15; i++) {
        cout<< arrB[i] << " ";
    }
    cout<< endl;   
    return 0;
}

运行结果：

归并排序的时间复杂度为：nlgn