- 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://www.codesnippet.cn/detail/130120148528.html
来源: http://www.codesnippet.cn/detail/130120148528.html