排序模板化

Java不支持预算符重载，我们通过实现Comparable接口达到相同的目的。当类实现了Comparable接口，则认为这个类的对象之间是可比较的。

当然java的基本类型实现了comparable接口只要用compareto方法就可以了大于0表示大于，小于0表示小于。

如果是自己的类要比较大小则需要继承comparable接口，实现compareto方法

以选择排序为例子，改为适用所有类型的排序算法

---

package bobo.algo;

import java.util.*;

public class SelectionSort {

// 我们的算法类不允许产生任何实例

    private SelectionSort(){}

public static void sort(Comparable[] arr){

int n = arr.length;

        for(int i =0 ; i < n; i ++ ){

// 寻找[i, n)区间里的最小值的索引

            int minIndex = i;

            for(int j = i +1 ; j < n; j ++ )

// 使用compareTo方法比较两个Comparable对象的大小

                if( arr[j].compareTo( arr[minIndex] ) <0 )

minIndex = j;

            swap( arr, i, minIndex);

        }

}

private static void swap(Object[] arr, int i, int j) {

Object t = arr[i];

        arr[i] = arr[j];

        arr[j] = t;

    }

public static void main(String[] args) {

// 测试Integer

        Integer[] a = {10,9,8,7,6,5,4,3,2,1};

        SelectionSort.sort(a);

        for(int i =0 ; i < a.length; i ++ ){

System.out.print(a[i]);

            System.out.print(' ');

        }

System.out.println();

        // 测试Double

        Double[] b = {4.4, 3.3, 2.2, 1.1};

        SelectionSort.sort(b);

        for(int i =0 ; i < b.length; i ++ ){

System.out.print(b[i]);

            System.out.print(' ');

        }

System.out.println();

        // 测试String

        String[] c = {"D", "C", "B", "A"};

        SelectionSort.sort(c);

        for(int i =0 ; i < c.length; i ++ ){

System.out.print(c[i]);

            System.out.print(' ');

        }

System.out.println();

        // 测试自定义的类Student

        Student[] d =new Student[4];

        d[0] =new Student("D",90);

        d[1] =new Student("C",100);

        d[2] =new Student("B",95);

        d[3] =new Student("A",95);

        SelectionSort.sort(d);

        for(int i =0 ; i < d.length; i ++ )

System.out.println(d[i]);

    }

}

---

package bobo.algo;

import java.util.*;

public class Studentimplements Comparable {

private String name;

    private int score;

    public Student(String name, int score){

this.name = name;

        this.score = score;

    }

// 定义Student的compareTo函数

    // 如果分数相等，则按照名字的字母序排序

    // 如果分数不等，则分数高的靠前

    @Override

public int compareTo(Student that) {

if(this.score < that.score )

return -1;

        else if(this.score > that.score )

return 1;

        else // this.score == that.score

            return this.name.compareTo(that.name);

    }

// 定义Student实例的打印输出方式

    @Override

public String toString() {

return "Student: " +this.name +" " + Integer.toString(this.score );

    }

}

---

当然可以自动生成测试数组

// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]

public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {

assert rangeL <= rangeR;//大于会抛出异常

    Integer[] arr =new Integer[n];

    for (int i =0; i < n; i++)

arr[i] =new Integer((int)(Math.random() * (rangeR - rangeL +1) + rangeL));

//random()方法产生的随机数在0.0和1.0之间，可能为0，但总是小于1，[0,1)   

return arr;

}