归并排序

归并排序是把两个或两个以上有序列表合并为一个新的有序列表。

归并排序的C实现(递归版本):

void merge(int *n, int len)
{
    if (len <= 1) return;

    int half = len / 2;
    merge(n, half);
    merge(n+half, len-half);

    int *_n = (int *) malloc(half * sizeof(int));
    memcpy(_n, n, half * sizeof(int));

    int i=0, j=half, k=0;
    while (i<half && j<len) {
        *(n+ k++) = *(n+j) < *(_n+i) ? *(n+ j++) : *(_n+ i++);
    }
    while (i<half) {
        *(n+ k++) = *(_n+ i++);
    }
    free(_n);
}

复杂度计算:

\begin{equation*} \left\{ \begin{array}{l} T(1) = 1 \\ T(n) = 2 T(\frac n 2) + n \end{array} \right. \end{equation*}

解之可得:

\begin{equation*} T(n) = n \log_2 n \end{equation*}

比较操作的次数介于\((n \log n)/2\)\(n \log n - n + 1\) 之间。赋值操作的次数是\(2n \log n\) 。归并算法的空间复杂度为:\(O(n)\) .

归并排序是唯一的稳定的复杂度为\(O(n \log n)\) 的排序算法。

comments powered by Disqus