排序--归并排序

了解归并

归并排序算法和快速排序算法是java.util.Arrays中使用的排序算法。对于一般的基本数据类型，Arrays.sort函数使用双轴快速排序算法，而对于对象类型使用归并排序（准确的说使用的是TimSort排序算法，它是归并排序的优化版本）。这样做的原因有两点，第一个原因，归并排序是稳定的，而快速排序不是稳定的。第二个原因，对于基本数据类型，排序的稳定性意义不大，但对于复合数据类型（比如对象）排序的稳定性就能帮助我们保持排序结果的某些性质。

归并排序也是一种基于分治法的排序。它是将原始无序序列划分成两个子序列，然后分别对每个子序列递归的进行排序，最后再将有序子序列进行合并。

---

自顶向下归并排序

自顶向下主要使用递归的思想，要保证整体序列有序，我们就应该同时保证原数组的左子序与右子序同时有序，然后将两个子序进行合并，然而要保证左子序和右子序有序，我们就要保证左子序的左右子序有序，然后进行合并；右子序的左右子序有序，然后进行合并… ….处理这种重复的工作，我们需要的就是递归。

图解自顶向下归并排序：

---

算法思想

• 既然我们要拆分数组，我们需要一个中枢值，它就是原数组的中点或近似中点的地方；
• 我们需要一个辅助空间，它用来保存当前需要合并的左右子序；
• 从图解中我们可以很清楚的看到，我们刚开始不断地将原数组拆分，直到保证每个子数组都有序，很显然，这个子数组就是单个元素；
• 合并子数组，将辅助数组中合并后产生的新数组覆盖至原数组，我们需要对原数组进行刷新。

下面是自顶向下的实现代码：

#include<iostream>
using namespace std;

#define SIZE 11

class MergeTD {
private:
    int *array_temp;

public:
    MergeTD(int array_temp[]) {
        this -> array_temp = array_temp;
    }

    //我对sort函数进行了重载
    void sort(int array[]);
    void merge(int array[], int mid, int l, int r);
    void sort(int array[], int l, int r);
};

void MergeTD :: sort(int array[]) {
    //进行归并排序，需要排序的数组和左右两个指标
    sort(array, 0, SIZE-1);
}

void MergeTD :: sort(int array[], int l, int r) {
    //当已经拆分为单个元素或l已经大于r的时候退出当前函数
    if(l >= r)
        return ;

    //计算中点值
    int mid = l+(r-l)/2;

    //对左边进行拆分
    sort(array, l, mid);
    //对右边进行拆分
    sort(array, mid+1, r);
    //进行归并操作
    merge(array, mid, l, r);
}

void MergeTD :: merge(int array[], int mid, int l, int r) {
    int m = l, n = mid+1;

    //将归并的数组存放到临时数组中
    for(int k = l; k <= r; k++) {
        array_temp[k] = array[k];
    }

    //归并操作在原数组上只对拆分的这一部分有效
    for(int i = l; i <= r; i++) {
        if(m > mid)
            array[i] = array_temp[n++];
        else if(n > r)
            array[i] = array_temp[m++];
        else if(array_temp[n] < array_temp[m])
            array[i] = array_temp[n++];
        else
            array[i] = array_temp[m++];
    }
}

int main()
{
    int array[SIZE];
    //辅助数组，用来存储每个有序的小数组
    int array_temp[SIZE];
    MergeTD TDMerge(array_temp);

    for(int i = 0; i < SIZE; i++) {
        cin >> array[i];
    }

    //归并排序
    TDMerge.sort(array);

    for(int i = 0; i < SIZE; i++) {
        cout << array[i] << ' ';
    }

    return 0;
}

---

效率分析

归并排序的时间主要花在了划分序列，子序列的排序过程以及合并过程，由于划分序列的时间为常数，对一个长度为n的记录序列进行归并排序，调用一趟归并排序的操作是调用n/2h次合并算法，时间复杂度为O(n)。整个归并排序需要进行logN趟归并操作，时间复杂度O(n) = NlogN。

空间复杂度：需要一个空间大小为N的辅助数组来存放待排序记录，空间杂度为O(n)。

最后，归并排序是稳定的。

---

自底向上归并排序

直接看图解吧：

可以看到在自顶向下归并排序中，我们先是对数组进行了不断的拆分，然后又合并，而在自底向上的归并中，我们不再对数组进行拆分，因为单个元素始终有序，所以我们只要刚开始控制子数组的长度为1，然后进行一一合并，合并后的子数组长度为2，那么我们就进行两两合并… …可以看到，自底向上的代码是比自顶向下的代码要好写的。

在这里我们需要注意的一点是数组按照归并长度划分，最后一个子数组可能不满足长度要求，这个情况需要特殊处理。自底向上一般使用循环：

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;

void sort(int array[], int size) {
    int aux[size];

    //刚开始子数组长度为1，然后进行一一归并，两两归并，四四归并... ...当子数组长度大于等于原数组长度时，整个数组有序
    for(int i = 1; i < size; i *= 2) {
        //将原数组复制到一个临时数组之中
        memcpy(aux, array, 4*size);

        //进行归并操作，首先要判断好每次归并的start，mid，end
        for(int start = 0; start < size; start += i*2) {
            int end = start + i*2-1;
            int mid = (start+end)/2;
            int m = start, n = mid+1;

            //当我们对数组进行划分的时候，最后一个子数组的end有时候会大于数组长度，此时我们应该选取整体数组的长度
            if(end >= size) {
                end = size-1;
            }

            //开始进行单趟归并
            for(int k = start; k <= end; k++) {
                if(m > mid) {
                    array[k] = aux[n++];
                } else if(n > end) {
                    array[k] = aux[m++];
                } else if(aux[m] > aux[n]) {
                    array[k] = aux[n++];
                } else {
                    array[k] = aux[m++];
                }
            }
        }
    }
}

int main()
{
    int *array;
    int size;

    cin >> size;
    array = (int *)malloc(sizeof(int)*size);

    for(int i = 0; i < size; i++) {
        cin >> array[i];
    }

    sort(array, size);

    for(int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }

    return 0;
}