排序算法-归并排序

二路归并排序主旨是“分解”与“归并”

分解：

1.将一个数组分成两个数组，分别对两个数组进行排序。

2.循环第一步，直到划分出来的“小数组”只包含一个元素，只有一个元素的数组默认为已经排好序。

归并：

1.将两个有序的数组合并到一个大的数组中。

2.从最小的只包含一个元素的数组开始两两合并。此时，合并好的数组也是有序的。

图1. 归并排序过程 图2. 合并两个有序数组

举例说明：

1.图中原始数组为{2,4,7,5,8,1,3,6}，数组中元素的个数为8个。首先将8个元素的数组二分，每次分解后，

数组中元素的数目为原数组的一半。直到分解为只含有一个元素的数组。

2.将小的数组按序合并，每次合并后数组的大小为上层数组的一倍。此时数组中的元素都是按序排列的。

3.在合并两个有序数组。如图2

void  merge(int * a, int low, int mid, int high)
{
    int i = low, j = mid + 1, p = 0;//对应a数组的下标
    int  r[high - low + 1];//申请另一个对应大小的数组来存放排好序的数据
    while (i <= mid && j <= high)
    {
        r[p++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= mid)
        r[p++] = a[i++];
    while (j <= high)
        r[p++] = a[j++];
    for (p = 0, i = low; i <= high; p++, i++)
        a[i] = r[p];//最后再把有序数据存进a数组中，使得a数组对应部分数据有序
}

void mergeSort(int k[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(k, low, mid); //归并排序前半段
        mergeSort(k, mid + 1, high); // 归并排序后半段
        
        merge(k, low, mid, high);
    }
}

迭代实现

#define MAXSIZE 10

void MergeSort(int k[], int n)
{
    int i, next, left_min, left_max, right_min, right_max;
    int *temp = (int *)malloc(n * sizeof(int));

    for( i=1; i < n; i*=2 ) 
    {
        for( left_min=0; left_min < n-i; left_min = right_max )
        {
            right_min = left_max = left_min + i;
            right_max = left_max + i;

            if( right_max > n )
            {
                right_max = n;
            }

            next = 0;

            while( left_min < left_max && right_min < right_max )
            {
                if( k[left_min] < k[right_min] )
                {
                    temp[next++] = k[left_min++];
                }
                else
                {
                    temp[next++] = k[right_min++];
                }
            }

            while( left_min < left_max )
            {
                k[--right_min] = k[--left_max];
            }

            while( next > 0 )
            {
                k[--right_min] = temp[--next];
            }
        }
    }
}