鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

排序算法之归并排序

来源:互联网 作者:佚名 时间:2015-09-25 05:37
归并 排序 的思想是分治思想。 第一, 归并 算法 :把两个拍好序的数组合并成一个拍好序的数组: void merge(int A[], int p, int q, int r) { int m = r - p + 1; int i = p, j = q + 1, k = 0; int* pb = new int[m]; while (i = q j = r) { if (A[i] = A[

 归并排序的思想是分治思想。

第一,归并算法:把两个拍好序的数组合并成一个拍好序的数组:

void merge(int A[], int p, int q, int r)
{
    int m = r - p + 1;
    int i = p, j = q + 1, k = 0;

    int* pb = new int[m];

    while (i <= q && j <= r)
    {
        if (A[i] <= A[j])
        {
            pb[k++] = A[i++];
        }
        else
        {
            pb[k++] = A[j++];
        }
    }

    while (i <= q)
    {
        pb[k++] = A[i++];
    }
    while (j <= r)
    {
        pb[k++] = A[j++];
    }

    for (i = p, k = 0; i <= r; i++, k++)
    {
        A[i] = pb[k];
    }

    delete [] pb;
}

 

第二,归并排序:把数组递归的分成两份,当每个数组都拍好序后,然后归并在一起。

void merge_sort(int A[], int n)
{
    int i, s, t = 1;
    while (t < n)
    {
        s = t;
        t = 2 * t;
        i = 0;

        while (i + t < n)
        {
             merge(A, i, i + s - 1, i + t - 1);
             i += t;
        }

        if (i + s < n)
        {
             merge(A, i, i + s - 1, n - 1);
        }
    }
}

网友评论
<