JAVA實現歸并排序

2019-11-06 06:25:17

字體：大中小

來源：轉載

供稿：網友

package tree;import java.util.ArrayList;import java.util.List;/** * Created by rightHead on 2017/3/6. */public abstract class MergeSort<T> { PRivate T[] result; public abstract boolean compare(T arg1, T arg2); public void sort(T[] s, int start, int end) { result = s; Sort(start, end); } private void Sort(int start, int end) { if (start >= end){ return; } T[] cache = result; List<T> group1 = new ArrayList<>(); List<T> group2 = new ArrayList<>(); int group1Start, group1End, group2Start, group2End; if (end - start == 1){ group1Start = group1End = start; group2Start = group2End = end; }else{ int temp = (start+end) >> 1; group1Start = start; group1End = temp; group2Start = temp+1; group2End = end; } for (int i=group1Start; i<=group1End; i++){ group1.add(cache[i]); } Sort(group1Start, group1End); group1.removeAll(group1); // 這個方法的效率未知 for (int i=group1Start; i<=group1End; i++){ group1.add(cache[i]); } for (int i=group2Start; i<=group2End; i++){ group2.add(cache[i]); } Sort(group2Start, group2End); group2.removeAll(group2); for (int i=group2Start; i<=group2End; i++){ group2.add(cache[i]); } int i=0,j=0,k=start; int group1Size = group1.size(); int group2Size = group2.size(); while (true){ if (compare(group1.get(i), group2.get(j))){ cache[k++] = group1.get(i++); }else{ cache[k++] = group2.get(j++); } if (i == group1Size){ while (j != group2Size){ cache[k++] = group2.get(j++); } return; } if (j == group2Size){ while (i != group1Size){ cache[k++] = group1.get(i++); } return; } } }} public static void main(String[] args) { MergeSort<Integer> mergeSort = new MergeSort<Integer>() { @Override public boolean compare(Integer arg1, Integer arg2) { return arg1 > arg2; } }; Integer[] xo = {8,4,7,5,9,2,1,3,0}; mergeSort.sort(xo, 0, xo.length-1); for (int s : xo){ System.out.println(s); } }

上一篇：java中大小寫字母轉換

下一篇：Java基礎學習（四）