分治法:归并排序

2015年12月29日 原创
关键词: C++ 数据结构 算法 分治法
摘要 归并排序是在速度上略逊于快速排序的一种排序算法,在对于随机排列的数据时,快速排序比归并排序要快,归并排序是一种典型的分治法的应用。

归并排序是成功应用分治技术的一个完美例子。对于一个需要排序的数组A[0..n-1],归并排序把它一分为二:A[0..n/2-1]和A[n/2...n-1],并对每个子数组递归排序,然后把这两个排好序的子数组合并为一个有序数组。

对两个有序数组的合并可以通过下面的算法完成。初始状态下,两个指针(数组下标)分别指向两个待合并数组的第一个元素。然后比较这两个元素的大小,将较小的元素添加到一个新创建的数组中。接着,被复制数组中的指针后移,指向该较小元素的后继元素。上述操作一直持续到两个数组中的一个被处理完为止。然后,在未处理完的数组中,剩下的元素被复制到新数组的尾部。

归并排序的算法效率如何呢?为简单起见,我们假设n是2的乘方,那么键值比较次数T(n)的递推关系式为:

当n>1时,T(n)=2C(n/2)+Tmerge(n),T(1)=0

根据主定理,我们可以证明T(n)为Θ(nlogn)。

归并排序在最坏情况下的键值比较次数十分接近于任何基于比较的排序算法在理论上能够达到的最少次数。归并排序的主要缺点就是该算法需要线性的额外空间。虽然合并也可以做到“在位”,但会导致算法更复杂。而且,因为它的增长次数具有一个很大的常系数,所以在位的合并排序算法只具有理论上的意义。

下面就是一个c++程序实现的在位的(即不申请多个数组)的归并算法。

#include<iostream>
using namespace std;
void merge(int* arr,int* temp, int start, int end) {
    int i = 0, j = 0, k = 0, mid = (start+end)/2;
    for (i = start, j = mid, k = start; i < mid && j < end;) {
        if (temp[i] < temp[j]) {
            arr[k++] = temp[i];
            i++;
        }
        else{
            arr[k++] = temp[j];
            j++;
        }
    }
    if (i == mid) {
        while (j != end) {
            arr[k++] = temp[j++];
        }
    }
    else {
        while (i != mid) {
            arr[k++] = temp[i++];
        }
    }
    for (int p = start; p < end; p++) {
        temp[p] = arr[p];
    }
}
void mergesort(int* arr,int* temp,int start, int end) {
    int mid = (start + end) / 2;
    if (end - start <= 1)
        return;
    for (int i = start; i < mid; i++) {
        temp[i] = arr[i];
    }
    for (int j = mid; j < end; j++) {
        temp[j] = arr[j];
    }
    mergesort(arr, temp, start, mid);
    mergesort(arr, temp, mid, end);
    merge(arr, temp, start, end);
}
int data[] = { 4, 9, 8, 7, 2, 58, 8, 3, 5, 849, 49, 5, 489, 41, 894, 984, 126, 156, 49, 84, 231, 56, 654, 98, 1, 65, 8, 1, 89, 1, 18, 0, 8, 498, 1, 894, 159, 198, 1 };
int main() {

    int temp[1000] = { 0 };
    mergesort(data, temp, 0, sizeof(data) / sizeof(int));

    for (int i = 0; i < sizeof(data) / sizeof(int); i++) {
        cout << data[i] << " ";
    }
    cout << endl;
    return 0;
}