排序算法之冒泡排序、选择排序、插入排序

  1 package org.guangsoft;
  2 
  3 import java.lang.reflect.InvocationHandler;
  4 import java.lang.reflect.Method;
  5 import java.lang.reflect.Proxy;
  6 import java.util.Arrays;
  7 
  8 public class SortAlgorithm {
  9 
 10     //排序算法接口
 11     interface Sort {
 12         //排序算法名称
 13         String sortName();
 14         //元素大小的判断
 15         static boolean greater(Comparable x, Comparable y) {
 16             return x.compareTo(y) > 0;
 17         }
 18         //交换元素
 19         static void swap(Comparable[] data, int i, int j) {
 20             Comparable temp = data[i];
 21             data[i] = data[j];
 22             data[j] = temp;
 23         }
 24         //排序方法
 25         Comparable[] sort(Comparable[] data);
 26     }
 27 
 28     //冒泡排序
 29     static class BubbleSort implements Sort {
 30         @Override
 31         public String sortName() {
 32             return "冒泡排序";
 33         }
 34         @Override
 35         public Comparable[] sort(Comparable[] data) {
 36             //需要进行n-1次范围筛选
 37             for(int i = data.length - 1; i > 0; i--) {
 38                 //在每次筛选的范围内将最大值冒泡到最后
 39                 for(int j = 0; j < i; j++) {
 40                     if(Sort.greater(data[j], data[j + 1])) {
 41                         Sort.swap(data, j, j + 1);
 42                     }
 43                 }
 44             }
 45             return data;
 46         }
 47     }
 48 
 49     //选择排序
 50     static class SelectionSort implements Sort {
 51         @Override
 52         public String sortName() {
 53             return "选择排序";
 54         }
 55         @Override
 56         public Comparable[] sort(Comparable[] data) {
 57             //需要进行n-1次范围筛选
 58             for(int i = 0; i < data.length - 1; i++) {
 59                 //在每次筛选的范围内将最小值放到最前
 60                 int minIndex = i;
 61                 for(int j = i + 1; j < data.length; j++) {
 62                     if(Sort.greater(data[minIndex], data[j])) {
 63                         minIndex = j;
 64                     }
 65                 }
 66                 Sort.swap(data, i, minIndex);
 67             }
 68             return data;
 69         }
 70     }
 71 
 72     //插入排序
 73     static class InsertionSort implements Sort {
 74         @Override
 75         public String sortName() {
 76             return "插入排序";
 77         }
 78         @Override
 79         public Comparable[] sort(Comparable[] data) {
 80             for(int i = 1; i < data.length; i++) {
 81                 for(int j = i; j > 0; j--) {
 82                     if(Sort.greater(data[j - 1], data[j])) {
 83                         Sort.swap(data, j - 1, j);
 84                     } else {
 85                         break;
 86                     }
 87                 }
 88             }
 89             return data;
 90         }
 91     }
 92 
 93     //动态代理测试器
 94     static class DynamicSort {
 95         //动态代理处理器
 96         static class SortInvocationHandler implements InvocationHandler {
 97             private Sort sort;
 98             SortInvocationHandler(Sort sort) { this.sort = sort;}
 99             @Override
100             public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
101                 System.out.printf("-------------测试%s算法-------------\n", sort.sortName());
102                 Comparable[] data = (Comparable[])args[0];
103                 System.out.printf("排序前数据：%s\n", Arrays.toString(data));
104                 long start = System.currentTimeMillis();
105                 data = (Comparable[]) method.invoke(sort, args);
106                 long end = System.currentTimeMillis();
107                 System.out.printf("排序后数据：%s\n", Arrays.toString(data));
108                 System.out.printf("排序总耗时：%s毫秒\n", end - start);
109                 return null;
110             }
111         }
112         //执行代理
113         public static void sort(Comparable[] data, Class clazz) throws Throwable {
114             Sort sort = (Sort) clazz.getDeclaredConstructor().newInstance();
115             sort = (Sort)Proxy.newProxyInstance(clazz.getClassLoader(), clazz.getInterfaces(), new SortInvocationHandler(sort));
116             sort.sort(data);
117         }
118     }
119 
120     //启动类
121     public static void main(String args[]) throws Throwable {
122         Integer[] data = {8, 4, 5, 7, 1, 3, 2, 6};
123         //测试冒泡排序
124         DynamicSort.sort(Arrays.copyOf(data, data.length), BubbleSort.class);
125         //测试选择排序
126         DynamicSort.sort(Arrays.copyOf(data, data.length), SelectionSort.class);
127         //测试插入排序
128         DynamicSort.sort(Arrays.copyOf(data, data.length), InsertionSort.class);
129     }
130 
131 }