浅谈排序算法实现 （归并排序）

       归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。      归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。    下面是博客http://blog.csdn.net/morewindows/article/details/6678165的内容：    首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。   

//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;

i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++]; 
}

while (i < n)
c[k++] = a[i++];

while (j < m)
c[k++] = b[j++];
}

   可以看出合并有序数列的效率是比较高的，可以达到O(n)。

      解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

     可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid,   n = last;
int k = 0;

while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}

while (i <= m)
temp[k++] = a[i++];

while (j <= n)
temp[k++] = a[j++];

for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp);    //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}

bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}

    题外：归并排序算法实现的效率相对前面介绍的（插入，冒泡，交换，快速）都要快很多。但是需要额外的声明空间去保存合并后的数据，而快速排序在应用中还是比较多的。这点只能根据个人情况去选择高效的排序方法。
 下面是个人实现的通用数据类型的函数接口。基本思想和上面的是一样的（C语言实现）

/*mgsort.c
 *归并排序，也是运用分治算法
 *
 */

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

/*************************************************************************
 * 将左右部分排序好的数组进行合并
 *参数：data :整个数组；    esize: 元素大小；
 *      i : 起始元素下标；j：中间元素下标； k：结束元素下标
 *      compare : 比较函数。
 *返回值： 0 成功 ；-1 失败。
 * **********************************************************************/
static int merge(void *data,int esize,int i,int j,int k,int(*compare)(const void *key1,const void *key2))
{
    char *a = data,
         *m = NULL;
    /*初始化变量*/
    int ipos = i,
        jpos = j + 1,
        mpos = 0;

    if (( m = (char *)malloc(esize*(( k - i) + 1))) == NULL )
        return -1;

    /*  i-> j 左半部分  （j + 1） -> k 右半部分 */
    while (ipos <= j || jpos <= k){ /* 数组还未遍历完*/
        if (ipos > j){/*左边部分遍历完，右半部分未完情况*/
            while (jpos <= k){
                memcpy (&m[mpos * esize], &a[jpos * esize],esize);
                jpos ++;
                mpos ++;
            }
            continue;
        } else if (jpos > k){ /*右半部分遍历完，左半部分未完*/
            while (ipos <= j){
                memcpy (&m[mpos * esize], &a[ipos * esize],esize);
                ipos ++;
                mpos ++;
            }
            continue;
        }

        /* 左右部分都未遍历完情况*/
        if (compare (&a[ipos * esize], &a[jpos * esize]) < 0){
                memcpy (&m[mpos * esize], &a[ipos * esize],esize);
                ipos ++;
                mpos ++;
        } else {
                memcpy (&m[mpos * esize], &a[jpos * esize],esize);
                jpos ++;
                mpos ++;
        }
    }
    /*讲合并完部分，在拷贝到数组data中*/
    memcpy(&a[i * esize], m, esize * ((k - i) + 1));

    free(m);
    return 0;
}

/*********************************************************
 *归并排序算法实现
 *参数 data:排序的数组;  size：数组元素个数  ; esize：元素的大小
 *     i：起始元素下标； k：结束元素下标;   compare:比较函数
 *返回值： 成功，0 失败 -1
 * *******************************************************/

int mgsort (void *data, int size, int esize , int i, int k, int (*compare)(const void *key1,const void *key2))
{
    int  j;
    if (i < k){
        j = (int)((i + k -1)/2);

        if (mgsort(data, size, esize, i, j, compare) < 0)
            return -1;
        if (mgsort(data, size, esize, j + 1, k, compare) < 0)
            return -1;

        if (merge(data, esize, i, j, k, compare) < 0)
            return -1;
    }
    return 0;
}

/*compare_int */
static int compare_int(const void *int1, const void * int2)
{
    printf("int1 = %d. int2 = %d \n",*(const int *)int1,*(const int *)int2);
    if (*(const int *)int1 > *(const int *)int2)
        return 1;
    else if (*(const int *)int1 < *(const int *)int2)
        return -1;
    else
        return 0;
}

int main()
{
    int a[7]={10,20,5,6,18,25,30};
    mgsort(a,7,sizeof(int),0,6,compare_int);
    int i;
    for (i =0 ; i< 7; i++)
        printf("%d\n",a[i]);
}