自底向上的归并排序

自底向上的归并排序(即非递归归并排序)方法，排序过程如下图：

 

首先两两归并，然后再归并元素数量加倍，这样的归并规程就像一颗二叉树。

在下面的代码中，函数mergeSort就是控制数组进行自底向上的归并的。m用于指定每次每个归并数组的归并元素的数量，i用于控制归并数组的选择（即指针的偏移）。在归并的时候（merge函数），使用一个辅助数组aux来进行归并，辅助数组aux是一个全局变量，大小应该与待排序数组一样，下面的代码中为了简单，直接设置成了15(即带排序数组a的大小)

#include <stdio.h>

#include <stdlib.h>

 

#define min(A, B) (A < B)? A:B

typedef char Item;

 

void mergeSort(Item a[], int l, int r);

void merge(Item a[], int start, int mid, int end);

 

Item aux[15];

/**

自底向上的归并排序

*/

int main() {

    int i;

    Item a[] = {'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};

    mergeSort(a, 0, 14);

    for(i = 0; i < 15; i++) {

        printf("%4c", a[i]);

    }

    return 0;

}

/*自底向上的归并排序方法*/

void mergeSort(Item a[], int l, int r) {

    int m, i;

    for(m = 1; m < r; m += m) {

        for(i = 0; (l+i+m-1) < r; i = i + m + m) {

            merge(a, l+i, l+i+m-1, min(l+i+m-1+m, r));

        }

    }

}

 

/**

改进的归并方法，这样就可以减少检测是否到队尾的比较次数

*/

void merge(Item a[], int start, int mid, int end) {

    int i, j, k;

    for(i = mid + 1; i > start; i--) aux[i-1] = a[i-1];

    for(j = mid; j < end; j++) aux[end+mid-j] = a[j+1];

 

    for(k = start; k <= end; k++)

        if(aux[i] < aux[j])

            a[k] = aux[i++];

        else

            a[k] = aux[j--];

}