各种 Sort 算法，包括 Quick Sort, Merge Sort, Heap Sort, Count Sort
1 package Sort; 2 3 public class Sort { 4 /* 5 * Quick Sort 6 * Time : O(n log n) 7 * Space : O(log n) -- stack frame 8 */ 9 private void quickSort(int[] arr) { 10 if (arr == null || arr.length < 2) 11 return; 12 helperQuick(arr, 0, arr.length-1); 13 return; 14 } 15 private void helperQuick(int[] arr, int left, int right) { 16 if (left >= right) 17 return; 18 int i = left, j = right; 19 int tmp = arr[i]; 20 while (i < j) { 21 while (i<j && arr[j] >= tmp) { 22 j--; 23 } 24 arr[i] = arr[j]; 25 while (i<j && arr[i] < tmp) { 26 i++; 27 } 28 arr[j] = arr[i]; 29 } 30 arr[i] = tmp; 31 helperQuick(arr, left, i-1); 32 helperQuick(arr, i+1, right); 33 } 34 /*--------------------------------------*/ 35 36 /* 37 * Merge Sort 38 * Time : O(n log n) 39 * Space : O(n) 40 */ 41 private void mergeSort(int[] arr) { 42 if (arr == null || arr.length < 2) 43 return; 44 helperMerge(arr, 0, arr.length-1); 45 } 46 private void helperMerge(int[] arr, int s, int t) { 47 if (s >= t) return; 48 int mid = s + (t - s) / 2; 49 helperMerge(arr, s, mid); 50 helperMerge(arr, mid+1, t); 51 merge(arr, s, mid, mid+1, t); 52 } 53 private void merge(int[] arr, int s1, int t1, int s2, int t2) { 54 int[] tmp = new int[t1 - s1 + t2 - s2 + 2]; 55 int i = s1, j = s2, run = 0; 56 while (i <= t1 && j <= t2) { 57 if (arr[i] < arr[j]) { 58 tmp[run++] = arr[i++]; 59 } else { 60 tmp[run++] = arr[j++]; 61 } 62 } 63 while (i <= t1) { 64 tmp[run++] = arr[i++]; 65 } 66 while (j <= t2) { 67 tmp[run++] = arr[j++]; 68 } 69 System.arraycopy(tmp, 0, arr, s1, tmp.length); 70 } 71 /*--------------------------------------*/ 72 73 /* 74 * Heap sort 75 * Time : O(n log n) 76 * Space : O(1) 77 */ 78 private void heapSort(int[] arr) { 79 for (int i = arr.length / 2; i >= 0; i--) { 80 siftDown(arr, i, arr.length); 81 } 82 for (int i = arr.length-1; i > 0; i--) { 83 swap(arr, 0, i); 84 siftDown(arr, 0, i); 85 } 86 } 87 private void siftDown(int[] arr, int parent, int length) { 88 int child = parent * 2 + 1; 89 while (child < length) { 90 if (child + 1 < length && arr[child] < arr[child + 1]) 91 child++; 92 if (arr[parent] < arr[child]) { 93 swap(arr, parent, child); 94 parent = child; 95 child = parent * 2; 96 } else break; 97 } 98 } 99 private void swap(int[] arr, int i, int j) { 100 int tmp = arr[i]; 101 arr[i] = arr[j]; 102 arr[j] = tmp; 103 } 104 /*--------------------------------------*/ 105 106 /* 107 * Count Sort 108 * - Given a certain Range 109 * - all keys in the array are between that range 110 * Time : O(n + k) 111 * Space : O(n + k) 112 */ 113 public void countSort(int[] arr) { 114 int[] range = new int[15]; 115 116 for (int i : arr) { 117 range[i]++; 118 } 119 int j = 0; 120 for (int i = 0; i < arr.length; i++) { 121 while (range[j] == 0) { 122 j++; 123 } 124 arr[i] = j; 125 range[j]--; 126 } 127 } 128 /*--------------------------------------*/ 129 130 public static void main(String[] args) { 131 Sort sort = new Sort(); 132 133 System.out.println("Quick Sort"); 134 int[] arr0 = {6, 9, 10, 7, 8, 5, 3, 4, 11, 2}; 135 sort.quickSort(arr0); 136 for (int i : arr0) 137 System.out.print(i+" "); 138 System.out.println(); 139 System.out.println(); 140 141 System.out.println("Merge Sort"); 142 int[] arr1 = {6, 9, 10, 7, 8, 5, 3, 4, 11, 2}; 143 sort.mergeSort(arr1); 144 for (int i : arr1) 145 System.out.print(i+" "); 146 System.out.println(); 147 System.out.println(); 148 149 System.out.println("Heap Sort"); 150 int[] arr2 = {6, 9, 10, 7, 8, 5, 3, 4, 11, 2}; 151 sort.heapSort(arr2); 152 for (int i : arr2) 153 System.out.print(i+" "); 154 System.out.println(); 155 System.out.println(); 156 157 System.out.println("Count Sort <range: 0 - 14>"); 158 int[] arr3 = {6, 9, 10, 7, 8, 5, 3, 4, 11, 2}; 159 sort.heapSort(arr3); 160 for (int i : arr3) 161 System.out.print(i+" "); 162 System.out.println(); 163 } 164 }