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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
| package org.example.sort;
public class MergeSort {
public static void merge(int[] a, int start, int mid, int end) { int[] temp = new int[end - start + 1]; int i = start; int j = mid + 1; int k = 0;
while (i <= mid && j <= end) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } while (i <= mid) { temp[k++] = a[i++]; } while (j <= end) { temp[k++] = a[j++]; } for (i = 0; i < k; i++) { a[start + i] = temp[i]; } temp = null; }
public static void mergeSortUpToDown(int[] a, int start, int end) { if (a == null || start >= end) { return; } int mid = (end + start) / 2; mergeSortUpToDown(a, start, mid); mergeSortUpToDown(a, mid + 1, end);
merge(a, start, mid, end); }
public static void mergeGroups(int[] a, int len, int gap) { int i; int towLen = 2 * gap;
for (i = 0; i + 2 * gap - 1 < len; i += (2 * gap)) { merge(a, i, i + gap - 1, i + 2 * gap - 1); } if (i + gap - 1 < len - 1) { merge(a, i, i + gap - 1, len - 1); } }
public static void mergeSortDownToUp(int[] a) { if (a == null) { return; } for (int n = 1; n < a.length; n *= 2) { mergeGroups(a, a.length, n); } }
public static void main(String[] args) { int[] a = {80,30,60,40,20,10,50,70}; mergeSortUpToDown(a, 0, a.length - 1); for (int i : a) { System.out.printf("%d ", i); } } }
|