算法基础三：分治算法---归并排序算法

一、算法描述与分析

二、伪代码

对于数组A,起始位置在p，最后一个元素在r。先分成两个序列，然后对左边和右边的序列分别排序，最后合并。

三、代码实现

1、算法代码

①Sort

import java.util.Comparator;
import java.util.List;

public class Sort {

    public static void mergeSort(List<Comparable> a, int p, int r, Comparator comp){
        if (p<r){//递归结束的判断条件
            int q = (p+r)/2;
            mergeSort(a,p,q,comp);
            mergeSort(a,q+1,r,comp);
            LinearList.merge(a,p,q,r,comp);
        }
    }

}

②LinearList

import java.util.Comparator;
import java.util.List;

public class LinearList {

    public static void merge(List<Comparable> a, int p, int q, int r, Comparator comp){
        int i,j,k;
        int n1 = q-p+1;
        int n2 = r-q;

        Comparable[] L = new Comparable[n1];
        Comparable[] R = new Comparable[n2];
        for (i=0;i<n1;i++)
            L[i] = a.get(p+i);

        for (j=0;j<n2;j++)
            R[j] = a.get(q+1+j);
        i=j=0;
        k=p;
        while (i<n1 && j<n2){
            if (comp.compare(L[i],R[j])<0)
                a.set(k++,L[i++]);
            else
                a.set(k++,R[j++]);
        }
        if (i<n1)
            for (;i<n1;i++)
                a.set(k++,L[i]);
        if (j<n2)
            for (;j<n2;j++)
                a.set(k++,R[j]);

    }

}

③Greater & Less

Greater

import java.util.Comparator;

public class Greater implements Comparator<Comparable> {
    public int compare(Comparable x, Comparable y){
        return x.compareTo(y);
    }
}

Less

import java.util.Comparator;

public class Less implements Comparator<Comparable> {
    @Override
    public int compare(Comparable o1, Comparable o2) {
        return o2.compareTo(o1);
    }
}

④测试

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

public class Test {
    public static void main(String[] args) {
        Integer a[] = {5,1,9,4,6,2,0,3,8,7},i;
        String b[] = {"ChongQing","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
        Double c[] = {8.5,6.3,1.7,9.2,0.5,2.3,4.1,7.4,5.9,3.7};
        ArrayList<Integer> A = new ArrayList<>();
        Vector<String> B = new Vector<>();
        LinkedList<Double> C = new LinkedList<>();

        for (Integer integer : a) {
            A.add(integer);
        }
        for (String s : b) {
            B.add(s);
        }
        for (Double aDouble : c) {;
            C.add(aDouble);
        }

        Sort.mergeSort((List) A,0,9,new Greater());
        Sort.mergeSort((List) B,0,5,new Less());
        Sort.mergeSort((List) C,0,9,new Greater());

        System.out.println(A);
        System.out.println(B);
        System.out.println(C);
    }
}