首页 > 代码库 > 归并排序算法

归并排序算法

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

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

本文地址:http://www.cnblogs.com/archimedes/p/merge-sort-algorithm.html,转载请注明源地址。

算法描述

归并操作的过程如下:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4. 重复步骤3直到某一指针到达序列尾

  5. 将另一序列剩下的所有元素直接复制到合并序列尾

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

归并操作

归并操作(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)codingwu   (mail: oskernel@126.com) // 博客地址:http://www.cnblogs.com/archimedes/#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;}

使用递归实现:

// Completed on 2014.10.11 17:20// Language: C99//// 版权所有(C)codingwu   (mail: oskernel@126.com) // 博客地址:http://www.cnblogs.com/archimedes/#include<stdio.h>#include<stdlib.h>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);    }}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;}

 

归并排序算法