排序就是对一串数组进行逻辑顺序重新排列的过程,即使现在库里面集成了全面的优秀排序算法,
但是我们学习算法实现也可以有助我们去比较各个算法的性能.
任何排序算法都是在树结构的基础上进行排序
假设一个数的高度为h,最好情况也为 2的h次方, 例如 16个点 = 2的4次方
h就是比较的次数,也就是4 = lg16 h= lgN(N为元素数量)
我们可以把排序算法大抵分为两类,一种是函数只需要自身不需要额外空间的原地排序.另一种则是,需要额外空间存储另一个数组副本的算法
然后我们为各类排序算法的API模板,定义一个模板
| package sortexample;
/** * * @author Heaven * 此为一个模板,是为了接下来各类排序算法的API模板 */ public class SortExample { public static void sort(Comparable<Object>[] a) {//进行排序的方法 } public static boolean less(Comparable<Object> a,Comparable<Object> b) {//对元素进行比较 return a.compareTo(b) < 0; } private static void exch(Comparable<Object>[] a,int i,int j) {//进行交换 Object n =a[i]; a[i] = a[j]; a[j] = (Comparable<Object>) n; } private static void show(Comparable<Object>[] a) { for (int i = 0; i < a.length; i++) { System.out.println(a[i]+” “); }//进行输出 } public static boolean isSorted(Comparable<Object>[] a) {//测试是否排序 for (int i = 1; i < a.length; i++) { if (less(a[i],a[i-1])) { return false; } } return true; } } |
并且要求,测试的数据类型必须实现了Comparable接口
仓库的地址在