数据结构-归并排序，数据结构归并排序,归并排序（泛型）[ Co

数据结构-归并排序，数据结构归并排序,归并排序（泛型）[ Co

归并排序（泛型）

[ Compare类见前面冒泡查找 ]

package com.algorithm.sorting;import java.util.ArrayList;import java.util.List;import com.algorithm.utils.Compare;/* * Merge sortting 归并排序 * time:O(N*logN) */public class Merge<E> {    /*     *  sort array     */    public void sort(E list[]) {         divide(list, 0, list.length - 1);    }    public void divide(E list[], int left, int right) {        if (left < right) {            int mid = (left + right) / 2;            divide(list, left, mid);// sort left            divide(list, mid + 1, right);// sort right            merge(list, left, mid, right);// merge        }    }    public void merge(E list[], int leftstart, int mid, int rightend) {        Compare compare = new Compare();        int start = leftstart;//必须单独记住开始下标 start        int leftend = mid;        int rightstart = mid + 1;        int k = 0;        int size = rightend - leftstart + 1;        E[] temp = (E[]) new Object[size];        while (leftstart <= leftend && rightstart <= rightend) {            if (compare.compare(list[leftstart], list[rightstart]) < 0) {                temp[k++] = list[leftstart++];            } else {                temp[k++] = list[rightstart++];            }        }        while (leftstart <= leftend) {            temp[k++] = list[leftstart++];        }        while (rightstart <= rightend) {            temp[k++] = list[rightstart++];        }        /*         * copy temp array back to list attention          * 必须单独记住开始下标 start         */        for (int i = 0; i < temp.length; i++) {            list[start + i] = temp[i];        }    }    /*     *  sort colllection     */    public List<E> sort(List<E> list) {        return divide(list, 0, list.size() - 1);    }    public List<E> divide(List<E> list, int left, int right) {        if (left < right) {            int mid = (left + right) / 2;            divide(list, left, mid);            divide(list, mid + 1, right);            merge(list, left, mid, right);        }        return list;    }    public void merge(List<E> list, int leftstart, int mid, int rightend) {        Compare compare = new Compare();        int start = leftstart;        int leftend = mid;        int rightstart = mid + 1;        int k = 0;        List<E> temp = new ArrayList<E>();        while (leftstart <= leftend && rightstart <= rightend) {            if (compare.compare(list.get(leftstart), list.get(rightstart)) <= 0) {                temp.add(k++, list.get(leftstart++));            } else {                temp.add(k++, list.get(rightstart++));            }        }        while (leftstart <= leftend) {            temp.add(k++, list.get(leftstart++));        }        while (rightstart <= rightend) {            temp.add(k++, list.get(rightstart++));        }        /*         * 因为集合的数据如果超出容量的话，集合会自动扩容，添加在尾部。         *  如果采用add方法的话，list集合会不断扩大，而不是达到交换数据目的。         * 所以应该采用set方法，修改数据，达到交换数据的目的。         */        for (int i = 0; i < temp.size(); i++) {            list.set(start + i, temp.get(i));        }    }}//该片段来自于http://byrx.net