3. 归并排序

归并排序以ø(N logN)最坏情形运行时间运行，而所使用的比较次数几乎是最优的。

这个算法的基本操作是合并两个已排序的表。

归并排序大致分为两种：

1. 自顶向下(递归)
2. 自底向上(迭代)

1. 实现

1.1 自顶向下递归排序

自顶向下的递归排序主要使用的是分治思想,代码实现较为复杂。

1.1.1 实现流程

1. 分配等同于待排序大小的内存空间。(必须且不会更少)
2. 对半分割，成两个不同的部分。
3. 重复2步骤直至不能再分割。
4. 对两部分分别排序。
5. 合并排序两部分。
6. 返回上一级递归。

1.1.2 代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int ElementType;

/* 归并排序入口程序 */
void MergeSort(ElementType source[], int n);

/* 二分程序 */
static void MSort(ElementType source[], ElementType tmpArr[], int left, int right);

/* 排序合并程序 */
static void Merge(ElementType source[], ElementType tmpArr[], int left, int rightPos, int right);

void MergeSort(ElementType source[], int n) {
    ElementType *tmpArr;

    tmpArr = (ElementType *) malloc(n * sizeof(ElementType));
    if (tmpArr != NULL) {
        MSort(source, tmpArr, 0, n - 1);
        free(tmpArr);
    } else {
        printf("No Space for tmp array!!!");
        exit(EXIT_FAILURE);
    }
}


static void MSort(ElementType source[], ElementType tmpArr[], int left, int right) {
    int center;

    if (left < right) {
        center = (left + right) / 2;
        MSort(source, tmpArr, left, center);
        MSort(source, tmpArr, center + 1, right);
        Merge(source, tmpArr, left, center + 1, right);
    }
}

static void Merge(ElementType source[], ElementType tmpArr[], int left, int rightPos, int right) {

    int tmpLeft = left;
    int leftEnd = rightPos - 1;
    int tmpRight = rightPos;
    int Num = right - left + 1;

    while (tmpLeft <= leftEnd && tmpRight <= right) {
        if (source[tmpLeft] < source[tmpRight]) {
            tmpArr[left++] = source[tmpLeft++];
        } else {
            tmpArr[left++] = source[tmpRight++];
        }
    }

    while (tmpLeft <= leftEnd) {
        tmpArr[left++] = source[tmpLeft++];
    }

    while (tmpRight <= right) {
        tmpArr[left++] = source[tmpRight++];
    }

    /* 把排好的tmp复制回原数组,由于左标志已经被移动因此用右标志向左移动倒叙放 */
    for (int i = 0; i < Num; ++i, right--) {
        source[right] = tmpArr[right];
    }

}

1.1.3 自顶向下缩短运行时间的几个Tips

1.1.3.1 对小规模数组使用插入排序

长度小于15，一般可将时间缩短10%~15%。

1.1.3.2 测试数组是否已经有序

如果a[mid]小于等于a[mid+1]，我们就认为数组已经是有序的并跳过merge()方法。

1.1.3.3 不将元素赋值到辅助数组

部分归并排序实现中会现将数组复制到辅助数组排序后再复制回去(本例中没有这么做)。这种操作是可以避免的。

1.2 自低向上归并排序

自底向上的思想是，先两两合并最小的，再四四合并相对小的，如此这般，直到我们将整个数组归并到一起。

1.2.1 实现流程

1. 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕

1.2.2 算法图解

插入排序 插入排序

1.2.3 代码实现

int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int*));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

2. 时间复杂度

最差时间复杂度 ø( nlog n )
最优时间复杂度 ø( n )
平均时间复杂度 ø( nlog n )

最差空间复杂度 ø( n )