Wu Yudong's Blog

归并排序（Merge sort）是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

一个归并排序的例子:对一个随机点的链表进行排序

算法描述

归并操作的过程如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

特点：归并排序是稳定的排序.即相等的元素的顺序不会改变, 速度仅次于快速排序，但较稳定。

归并操作

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如：设有数列 [6，202，100，301，38，8，1]

初始状态：6, 202, 100, 301, 38, 8, 1

第一次归并后：[6, 202], [100, 301], [8, 38], [1]，比较次数：3；

第二次归并后：[6, 100, 202, 301]，[1, 8, 38]，比较次数：4；

第三次归并后：[1, 6, 8, 38, 100, 202, 301]，比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

算法实现

// Completed on 2014.10.11 17:20
// Language: C99
//
// 版权所有（C）wuyudong
// 博客地址：http://www.wuyudong.com
#include<stdio.h>
#include<stdlib.h>
void merge_sort(int *list, const int first, const int last)
{
    int len= last-first+1;  
    int left_min,left_max;    //左半区域边界 
    int right_min,right_max;  //右半区域边界 
    int index;
    int i;
    int *tmp;
    tmp = (int *)malloc(sizeof(int)*len);
    if( tmp == NULL || len <= 0 )
        return;
    
    for( i = 1; i < len; i *= 2 )
    {
        for( left_min = 0; left_min < len - i; left_min = right_max)
        {
            int j;
            right_min = left_max = left_min + i;
            right_max = left_max + i;
            j = left_min;
            if ( right_max > len )
                right_max = len;
            index = 0;
            while( left_min < left_max && right_min < right_max )
            {
                tmp[index++] = (list[left_min] > list[right_min] ? list[right_min++] : list[left_min++]);
            }
            while( left_min < left_max )
            {
                list[--right_min] = list[--left_max];
            }
            while( index > 0 )
            {
                list[--right_min] = tmp[--index];
            }
        }
    }
    free(tmp);
}
int main()
{
    int a[] = {288, 52, 123, 30, 212, 23, 10, 233};
    int n, mid;
    n = sizeof(a) / sizeof(a[0]);
    mid = n / 2;
    merge_sort(a, 0, n - 1);
    for(int k = 0; k < n; k++)
        printf("%d ", a[k]);
    printf("\n");
    return 0;
}

使用递归实现：

void merge(int *array,const int first, const int mid, const int last)
{
    int i,index;
    int first1,last1;
    int first2,last2;
    int *tmp;
    tmp = (int *)malloc((last-first+1)*sizeof(int));
    if( tmp == NULL )
        return;
    first1 = first;
    last1  = mid;
    first2 = mid+1;
    last2  = last;
    index = 0;
    while( (first1 <= last1) && (first2 <= last2) )
    {
        if( array[first1] < array[first2] )
        {
            tmp[index++] = array[first1];
            first1++;
        }
        else{
            tmp[index++] = array[first2];
            first2++;
        }
    }
    while( first1 <= last1 )
    {
        tmp[index++] = array[first1++];
    }
    while( first2 <= last2 )
    {
        tmp[index++] = array[first2++];
    }
    for( i=0; i<(last-first+1); i++)
    {
        array[first+i] = tmp[i];
    }
    free(tmp);
}
void merge_sort(int *array, const int first, const int last)
{
    int mid = 0;
    if(first < last)
    {
        mid = (first + last) / 2;
        merge_sort(array, first, mid);
        merge_sort(array, mid + 1, last);
        merge(array, first, mid, last);
    }
}

归并排序算法

Comments