算法设计与分析实践-作业4

1. 问题

• 二分归并排序：对n个不同的数构成的数组A[1…n]进行排序，其中n=2^k

2. 解析

图片来自网络，大概能表达意思。

3. 设计

因为归并排序只能归并两个有序数组，我们利用分治策略将要归并的两个数组再各自切分，直到最后数组中只剩一个元素，那么他一定是有序的，可以使用归并排序一层层整合。简单来说二分归并排序=分治策略+归并排序。

下面展示一些 内联代码片。

// A code block
var foo = 'bar';

void merge(int* a, int* c, int L, int R)
{
    int mid = (L + R) >> 1;
    int i = L, j = mid + 1, k = L;
    while (i <= mid && j <= R)    //将 a 数组分成左右两边，归并到 c 数组
    {
        if (a[i] <= a[j])
            c[k++] = a[i++];
        else
            c[k++] = a[j++];
    }
    while (i <= mid)
        c[k++] = a[i++];
    while (j <= R)
        c[k++] = a[j++];
    for (i = L; i <= R; i++)
        a[i] = c[i];
}

下面展示一些 内联代码片。

// A code block
var foo = 'bar';

void mergeSort(int* a, int* c, int L, int R)
{
    if (L == R)
        return;
    int mid = (L + R) >> 1;
    mergeSort(a, c, L, mid);
    mergeSort(a, c, mid + 1, R);
    merge(a, c, L, R);
}

4.分析：

算法复杂度分析：

W(n)=2W(n/2)+n-1
W(1)=0
可得：W(n)=nlogn-n+1

5. 源码

https://github.com/Ericjin1022/-suanfa