合并排序
将数列不停的拆分,直到只剩下一个元素,此时必然有序,然后将拆分的部分两两合并,最后成为一个有序数列。
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
| import java.util.Comparator; import java.util.LinkedList;
import static java.lang.System.out;
public class MergeSort<T> { private Comparator<T> comparator;
public void sort(LinkedList<T> s) { int size = s.size(); if (1 >= size) return; LinkedList<T> s1 = new LinkedList<>(); LinkedList<T> s2 = new LinkedList<>(); while (!s.isEmpty()) { s1.addLast(s.removeFirst()); if (!s.isEmpty()) s2.addLast(s.removeFirst()); } sort(s1); sort(s2); merge(s, s1, s2); }
private void merge(LinkedList<T> container, LinkedList<T> s1, LinkedList<T> s2) { while (!s1.isEmpty() || !s2.isEmpty()) { T e; if (s1.isEmpty()) { e = s2.removeFirst(); } else if (s2.isEmpty()) { e = s1.removeFirst(); } else if (comparator.compare(s1.getFirst(), s2.getFirst()) > 0) { e = s2.removeFirst(); } else { e = s1.removeFirst(); } container.addLast(e); } }
public MergeSort(Comparator<T> comparator) { this.comparator = comparator; }
public static void main(String[] args) { MergeSort<Integer> sort = new MergeSort<>((o1, o2) -> { if (o1 < o2) return -1; if (o1 > o2) return 1; return 0; }); LinkedList<Integer> list=new LinkedList<>(); list.add(0); list.add(8); list.add(6); list.add(9); list.add(7); list.add(2); list.add(4); list.add(3); list.add(5); list.add(1); sort.sort(list); list.forEach(out::print); } }
|