各种排序是常见的面试题， 我希望能够帮助大家轻松的秒杀那些小菜鸟

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

#define MAX_NUM 10

void mergeSort(int a[], int left, int right);

void merge(int a[], int left, int m, int right);

int main(void)
{
    int a[MAX_NUM] = {1, 3, 2, 1, 6, 1, 5, 8, 1, 0};
    int i;

    mergeSort(a, 0, MAX_NUM-1);
   
    for (i = 0; i < MAX_NUM; i++)
    {
        printf("%d ", a[i]);
    }

    getchar();
    return 0;
}

void merge(int a[], int left, int m, int right)
{
    int aux[MAX_NUM] = {0};
    int i, j, k;

    for (i = left, j = m+1, k = 0; k <= right-left; k++)
    {
        if (i == m+1)
        {
            aux[k] = a[j++];
            continue;
        }

        if (j == right+1)
        {
            aux[k] = a[i++];
            continue;
        }

        if (a[i] < a[j])
        {
            aux[k] = a[i++];
        }
        else
        {
            aux[k] = a[j++];
        }
    }

    for (i = left, j = 0; i <= right; i++, j++)
    {
        a[i] = aux[j];
    }
}

void mergeSort(int a[], int left, int right)
{
    int m = (right + left) / 2;

    if (right <= left)
        return ;

    mergeSort(a, left, m);
    mergeSort(a, m+1, right);
    merge(a, left, m, right);
}


[ 本帖最后由 BlueGuy 于 2011-1-7 22:54 编辑 ]

严格的说，这代码属于我半原创代码， 网络上应该找不到第二份这样的简单的~~~

优秀在于，你能看的懂，

如果按照 2^n 个数 调用 排序函数， 可以清楚的看到 归并排序的 分治树 是一棵完全二叉树， 如下
    mergeSort(0, 7): 1
        mergeSort(0, 3): 2
            mergeSort(0, 1): 3
                mergeSort(0, 0): 4
                mergeSort(1, 1): 4
            mergeSort(2, 3): 3
                mergeSort(2, 2): 4
                mergeSort(3, 3): 4
        mergeSort(4, 7): 2
            mergeSort(4, 5): 3
                mergeSort(4, 4): 4
                mergeSort(5, 5): 4
            mergeSort(6, 7): 3
                mergeSort(6, 6): 4
                mergeSort(7, 7): 4

如果换个方式打印， 又可以清楚的看到  归并排序的 合并过程属于 后序遍历二叉树，如下
    mergeSort(0, 3)
        mergeSort(0, 1)
            mergeSort(0, 0)
            mergeSort(1, 1)
            merge(0, 0, 1)
        mergeSort(2, 3)
            mergeSort(2, 2)
            mergeSort(3, 3)
            merge(2, 2, 3)
        merge(0, 1, 3)
    mergeSort(4, 7)
        mergeSort(4, 5)
            mergeSort(4, 4)
            mergeSort(5, 5)
            merge(4, 4, 5)
        mergeSort(6, 7)
            mergeSort(6, 6)
            mergeSort(7, 7)
            merge(6, 6, 7)
        merge(4, 5, 7)
    merge(0, 3, 7)

[ 本帖最后由 BlueGuy 于 2011-1-7 22:44 编辑 ]