首页 > 基础算法 > 排序 > 排序和查找(5)-归并排序
2014
03-24

排序和查找(5)-归并排序

归并排序是一个分治算法。归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列。merg() 函数是用来合并两个已有序的数组.  是整个算法的关键。看下面的描述对mergeSort函数的描述:

MergeSort(arr[], l,  r)
If r > l
     1. 找到中间点,讲arr分为两部分:  
             middle m = (l+r)/2
     2. 对一部分调用mergeSort :   
             Call mergeSort(arr, l, m)
     3.对第二部分调用mergeSort:
             Call mergeSort(arr, m+1, r)
     4. 合并这两部分:
             Call merge(arr, l, m, r)

下图来自维基百科,显示了完整的归并排序过程。例如数组{38, 27, 43, 3, 9, 82, 10}.

Merge-Sort

下面是C程序的实现:

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

/*合并arr的左右两部分: arr[l..m] 和 arr[m+1..r]  */
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* create temp arrays */
    int L[n1], R[n2];

    /* 复制数据到 L[] 和 R[] */
    for(i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(j = 0; j <= n2; j++)
        R[j] = arr[m + 1+ j];

    /* 将两部分再合并到 arr[l..r]*/
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* 复制剩下的部分 L[] */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* 复制剩下的部分 R[] */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* 对数据arr排序,从l到r */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2; //和 (l+r)/2 一样, 但是可以避免溢出在 l 和 r较大时
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

/*测试程序 */
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

时间复杂度:O(nlogn) 空间复杂度:O(n)    稳定排序

归并排序的应用:

1) 对链表进行排序。其它排序算法如堆排序和快速排序不能对链表排序。参考:使用归并排序对链表进行排序

2) 计算一个数组中的逆序对。剑指offer(09)-数组中的逆序对[分治]

3) 外排序

如果发现文中有不对的地方请发表您的评论。


  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience