算法导论2--分治算法合并排序

分治算法的步骤

分治法解题的一般步骤:
(1)分解,将要解决的问题划分成若干规模较小的同类问题;
(2)求解,当子问题划分得足够小时,用较简单的方法解决;
(3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

合并排序算法 伪代码

megre(a,p,q,r)
n1=q-p+1
n2=r-q
create arrays L[0,1,...n1] and R[0,1,..n2]
for i=0 to n1
    L[i]=a[p+i]
for j=0 to n2
    R[j]=a[q+1+j]
i=0
j=0
for k=p to r+1
    if j==n2||(i!=n1&&L[i]<R[j])
        A[k]=L[i]
        i=i+1
    else if i==n1||(j!=n2&&L[i]>=R[j])
        A[k]=R[j]
        j=j+1

megre-sort(a,p,r)
if p<r 
    q=(p+r)/2
    megre-sort(a,p,q)
    megre-sort(a,q+1,r)
    megre(a,p,q,r)

算法实现过程

合并排序

java代码实现

public class Test {

    public static void main(String[] args) {
        Test t = new Test();
        int[] a = new int[] { 7, 1, 6, 5, 3, 4, 2 };
        t.sort(a);
        t.out(a);
    }

    public void sort(int[] a) {
        margesort(a,0,a.length-1);
    }

    public void margesort(int[] a, int p, int r) {
        if (p < r) {
            int q = (p + r) / 2;
            margesort(a, p, q);
            margesort(a, q + 1, r);
            marge(a, p, q, r);
        }
    }

    public void marge(int[] a, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] l = new int[n1];
        int[] ri = new int[n2];
        for (int i = 0; i < n1; i++) {
            l[i] = a[p + i];
        }
        for (int j = 0; j < n2; j++) {
            ri[j] = a[q + 1 + j];
        }
        System.out.println();
        System.out.println("转换过程: ");
        out(a);
        System.out.println();
        System.out.println("-----");
        System.out.println("left: ");
        out(l);
        System.out.println();
        System.out.println("rigth: ");
        out(ri);
        System.out.println();
        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (j == n2 || (i!=n1&&l[i] < ri[j])) {
                a[k] = l[i];
                i++;
            } else if (i == n1 || (j!=n2&&l[i] >= ri[j])) {
                a[k] = ri[j];
                j++;
            }

        }
        out(a);
        System.out.println();

    }
    public void out(int[] a) {
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
}

转换过程

转换过程: 
7 1 6 5 3 4 2 
-----
left: 
7 
rigth: 
1 
1 7 6 5 3 4 2 

转换过程: 
1 7 6 5 3 4 2 
-----
left: 
6 
rigth: 
5 
1 7 5 6 3 4 2 

转换过程: 
1 7 5 6 3 4 2 
-----
left: 
1 7 
rigth: 
5 6 
1 5 6 7 3 4 2 

转换过程: 
1 5 6 7 3 4 2 
-----
left: 
3 
rigth: 
4 
1 5 6 7 3 4 2 

转换过程: 
1 5 6 7 3 4 2 
-----
left: 
3 4 
rigth: 
2 
1 5 6 7 2 3 4 

转换过程: 
1 5 6 7 2 3 4 
-----
left: 
1 5 6 7 
rigth: 
2 3 4 
1 2 3 4 5 6 7 

转载于:https://my.oschina.net/u/3706181/blog/1596787

版权声明:本文为weixin_34297300原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_34297300/article/details/92401313