返回顶部

收藏

数据结构-归并排序

更多

归并排序(泛型)

[ 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://outofmemory.cn

标签:java,算法

收藏

0人收藏

支持

0

反对

0

发表评论