data.txt
1 8,10,211,4,128,12,5,365,9,192,7,1,3,2,6,1024,11,13,20,54
SortAlgorithm.java
1 package io.guangsoft; 2 3 import java.io.FileInputStream; 4 import java.lang.reflect.InvocationHandler; 5 import java.lang.reflect.Method; 6 import java.lang.reflect.Proxy; 7 import java.nio.ByteBuffer; 8 import java.nio.channels.FileChannel; 9 import java.util.Arrays; 10 11 public class SortAlgorithm { 12 13 //排序算法接口 14 interface Sort { 15 //排序算法名称 16 String sortName(); 17 //元素大小的判断 18 static boolean greater(Comparable x, Comparable y) { 19 return x.compareTo(y) > 0; 20 } 21 //交换元素 22 static void swap(Comparable[] data, int i, int j) { 23 Comparable temp = data[i]; 24 data[i] = data[j]; 25 data[j] = temp; 26 } 27 //排序方法 28 Comparable[] sort(Comparable[] data); 29 } 30 31 //冒泡排序 32 static class BubbleSort implements Sort { 33 @Override 34 public String sortName() { 35 return "冒泡排序"; 36 } 37 @Override 38 public Comparable[] sort(Comparable[] data) { 39 //需要从由大到小范围进行n-1次筛选 40 for(int i = 0; i < data.length - 1; i++) { 41 //在每次筛选的范围内逐个比较，将最小值冒泡到范围最左端 42 for(int j = data.length - 1; j > i; j--) { 43 if(Sort.greater(data[j - 1], data[j])) { 44 Sort.swap(data, j - 1, j); 45 } 46 } 47 } 48 return data; 49 } 50 } 51 52 //选择排序 53 static class SelectionSort implements Sort { 54 @Override 55 public String sortName() { 56 return "选择排序"; 57 } 58 @Override 59 public Comparable[] sort(Comparable[] data) { 60 //需要从由大到小范围进行n-1次筛选 61 for(int i = 0; i < data.length - 1; i++) { 62 //在每次筛选的范围内选出最小值，将最小值交换到范围最左端 63 int minIndex = i; 64 for(int j = i + 1; j < data.length; j++) { 65 if(Sort.greater(data[minIndex], data[j])) { 66 minIndex = j; 67 } 68 } 69 Sort.swap(data, i, minIndex); 70 } 71 return data; 72 } 73 } 74 75 //插入排序 76 static class InsertionSort implements Sort { 77 @Override 78 public String sortName() { 79 return "插入排序"; 80 } 81 @Override 82 public Comparable[] sort(Comparable[] data) { 83 //需要从由小到大范围进行n-1次筛选 84 for(int i = 1; i < data.length; i++) { 85 //在每次筛选的范围内将新增元素插入到有序位置 86 for(int j = i; j > 0; j--) { 87 if(Sort.greater(data[j - 1], data[j])) { 88 Sort.swap(data, j - 1, j); 89 } else { 90 break; 91 } 92 } 93 } 94 return data; 95 } 96 } 97 98 //希尔排序 99 static class ShellSort implements Sort { 100 @Override 101 public String sortName() { 102 return "希尔排序"; 103 } 104 @Override 105 public Comparable[] sort(Comparable[] data) { 106 int gap = 1; 107 //确定初始增量 108 while(gap < data.length / 2) { 109 gap = 2 * gap + 1; 110 } 111 //逐步二分缩小排序增量 112 while(gap >= 1) { 113 //从中间位置开始向后逐步分组 114 for(int i = gap; i < data.length; i++) { 115 //组内进行插入排序 116 for(int j = i; j >= gap; j -= gap) { 117 if(Sort.greater(data[j - gap], data[j])) { 118 Sort.swap(data, j - gap, j); 119 } else { 120 break; 121 } 122 } 123 } 124 //缩小gap 125 gap >>>= 1; 126 } 127 return data; 128 } 129 } 130 131 //归并排序 132 static class MergeSort implements Sort { 133 private static Comparable[] assist; 134 @Override 135 public String sortName() { 136 return "归并排序"; 137 } 138 @Override 139 public Comparable[] sort(Comparable[] data) { 140 assist = new Comparable[data.length]; 141 int lo = 0; 142 int hi = data.length - 1; 143 sort(data, lo, hi); 144 return data; 145 } 146 //递归体 147 private static void sort(Comparable[] data, int lo, int hi) { 148 if(hi <= lo) return; 149 int mid = lo + (hi - lo) / 2; 150 sort(data, lo, mid); 151 sort(data, mid + 1, hi); 152 merge(data, lo, mid, hi); 153 } 154 //合并 155 private static void merge(Comparable[] data, int lo, int mid, int hi) { 156 //定义三个指针 157 int i = lo, p1 = lo, p2 = mid + 1; 158 //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处 159 while(p1 <= mid && p2 <= hi) { 160 if(!Sort.greater(data[p1], data[p2])) { 161 assist[i++] = data[p1++]; 162 } else { 163 assist[i++] = data[p2++]; 164 } 165 } 166 //遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处 167 while(p1 <= mid) { 168 assist[i++] = data[p1++]; 169 } 170 //遍历，如果p2指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处 171 while(p2 <= hi) { 172 assist[i++] = data[p2++]; 173 } 174 //把辅助数组中的元素拷贝到原数组中 175 for(int index = lo; index <= hi; index++) { 176 data[index] = assist[index]; 177 } 178 } 179 } 180 181 //快速排序 182 static class QuickSort implements Sort { 183 @Override 184 public String sortName() { 185 return "快速排序"; 186 } 187 @Override 188 public Comparable[] sort(Comparable[] data) { 189 int lo = 0, hi = data.length - 1; 190 sort(data, lo, hi); 191 return data; 192 } 193 //递归体 194 private static void sort(Comparable[] data, int lo, int hi) { 195 if(hi <= lo) return; 196 int partition = partition(data, lo, hi); 197 sort(data, lo, partition - 1); 198 sort(data, partition + 1, hi); 199 } 200 //分组 201 private static int partition(Comparable[] data, int lo, int hi) { 202 //确定分界值 203 Comparable key = data[lo]; 204 //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置 205 int left = lo, right = hi + 1; 206 //切分 207 while(true) { 208 //先从左往右扫描，移动right指针，找到一个比分界值小的元素，停止 209 while(!Sort.greater(key, data[--right])) { 210 if(right == lo) break; 211 } 212 //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止 213 while(!Sort.greater(data[++left], key)) { 214 if(left == hi) break; 215 } 216 //判断left>=right，如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可 217 if(left >= right) { 218 break; 219 } else { 220 Sort.swap(data, left, right); 221 } 222 } 223 //交换分界值 224 Sort.swap(data, lo, right); 225 return right; 226 } 227 } 228 229 //动态代理执行测试 230 static class DynamicSort { 231 //动态代理处理器 232 static class SortInvocationHandler implements InvocationHandler { 233 private Sort sort; 234 SortInvocationHandler(Sort sort) { this.sort = sort;} 235 @Override 236 public Object invoke(Object proxy, Method method, Object[] args) throws Throwable { 237 System.out.printf("-------------测试%s算法------------- ", sort.sortName()); 238 Comparable[] data = (Comparable[])args[0]; 239 System.out.printf("排序前数据：%s ", Arrays.toString(data)); 240 long start = System.currentTimeMillis(); 241 data = (Comparable[]) method.invoke(sort, args); 242 long end = System.currentTimeMillis(); 243 System.out.printf("排序后数据：%s ", Arrays.toString(data)); 244 System.out.printf("排序总耗时：%s毫秒 ", end - start); 245 return null; 246 } 247 } 248 //执行代理 249 public static void sort(Comparable[] data, Class clazz) throws Throwable { 250 Sort sort = (Sort) clazz.getDeclaredConstructor().newInstance(); 251 sort = (Sort)Proxy.newProxyInstance(clazz.getClassLoader(), clazz.getInterfaces(), new SortInvocationHandler(sort)); 252 sort.sort(data); 253 } 254 } 255 256 //NIO加载数据 257 public static<T> T[] loadData(Class<T> c) throws Throwable{ 258 FileInputStream fileInputStream = new FileInputStream(Sort.class.getClassLoader().getResource("data.txt").getPath()); 259 FileChannel fileChannel = fileInputStream.getChannel(); 260 ByteBuffer byteBuffer = ByteBuffer.allocate(1024); 261 StringBuffer stringBuffer = new StringBuffer(); 262 int length = -1; 263 while((length = fileChannel.read(byteBuffer)) != -1) { 264 byteBuffer.clear(); 265 byte[] bytes = Arrays.copyOf(byteBuffer.array(), length); 266 stringBuffer.append(new String(bytes)); 267 } 268 fileChannel.close(); 269 fileInputStream.close(); 270 return (T[]) Arrays.stream(stringBuffer.toString().split(",")).mapToInt(Integer::valueOf).boxed().toArray(Integer[]::new); 271 } 272 273 //启动类 274 public static void main(String args[]) throws Throwable { 275 Comparable[] data = loadData(Integer.class); 276 //测试冒泡排序 277 DynamicSort.sort(Arrays.copyOf(data, data.length), BubbleSort.class); 278 //测试选择排序 279 DynamicSort.sort(Arrays.copyOf(data, data.length), SelectionSort.class); 280 //测试插入排序 281 DynamicSort.sort(Arrays.copyOf(data, data.length), InsertionSort.class); 282 //测试希尔排序 283 DynamicSort.sort(Arrays.copyOf(data, data.length), ShellSort.class); 284 //测试归并排序 285 DynamicSort.sort(Arrays.copyOf(data, data.length), MergeSort.class); 286 //测试快速排序 287 DynamicSort.sort(Arrays.copyOf(data, data.length), QuickSort.class); 288 } 289 290 }
运行结果
