归并排序

归并排序 算法

算法思想

前期准备：归并排序利用的是分治法思想，其重复的子问题是如何归并两个有序数组a[]和b[]到c[]，这里实现为MergeOrderedArray。

具体思路：数组A，分成两个数组B、C，但是B、C不一定就是有序的，要不断地分，直至子数组都只有1个元素，当然有序，再合并起来，那么A就排序完毕了。这样通过先递归的分解数组，再合并数组就完成了归并排序。

算法实现

//将二个有序数列a[first...mid]和a[mid...last]合并。  
void MergeOrderedArray(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) > 1;  
        MergeSort(a, first, mid, temp);  //左边有序  
        MergeSort(a, mid + 1, last, temp);  //右边有序  
        MergeOrderedArray(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;  
}