聂永的博客

/**
 * 对象数组排序算法，藉此复习几种常见排序算法
 * 
 * 模板模式
 * 
 **/
public abstract class Sort {

 /**
  * 对象数组排序
  * @param <T>
  * @param ts 传入要排序的对象数组
  * @param c 需要传入的自定义比较器
  */
 public abstract <T> void sort(T[] ts, Comparator<? super T> c);

 /**
  * 对象数组排序
  * @param <T>
  * @param datas 传入的对象必须已经实现了Comparable接口
  */
 public <T extends Comparable<T>> void sort(T[] datas) {
  sort(datas, new ComparatorAdapter<T>());
 }

 /**
  * 定义一个比较适配器内部类,使Comparable接口适配成Comparator接口
  * 
  * @author xiaomin
  * 
  * @param <T>
  */
 private class ComparatorAdapter<T extends Comparable<T>> implements
   Comparator<T> {
  public int compare(T o1, T o2) {
   return o1.compareTo(o2);
  }
 }

 /**
  * 交换对象数组里面的两个元素位置
  * @param <T>
  * @param ints
  * @param index1
  * @param index2
  */
 protected <T> void swap(T[] ints, int index1, int index2) {
  T temp = ints[index1];

  ints[index1] = ints[index2];

  ints[index2] = temp;
 }
}

/**
 * 冒泡排序----交换排序的一种
 * 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
 * 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4
 *
**/
public class Bubble extends Sort{

 @Override
 public <T> void sort(T[] datas, Comparator<? super T> c){
  for(int i = (datas.length - 1); i > 0; i--){
   for(int j = 0; j < i; j++){
    if(c.compare(datas[j], datas[j + 1]) > 0){
     super.swap(datas, j, j+1);
    }
   }
  }
 }

 public static void main(String ... args){
  Bubble b = new Bubble();
  Integer [] ints = {1, 23, 0, 2, 356, 367, 6,-1, 256};
  b.sort(ints);
  
  System.out.println(Arrays.toString(ints));
 }
}

/**
 * 插入排序
 * 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。
 * 性能：比较次数O(n^2),n^2/4
 *       复制次数O(n),n^2/4
 *       比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
 *
 */
public class Insert extends Sort{

 @Override
 public <T> void sort(T[] datas, Comparator<? super T> c){
  for(int i = 0; i < datas.length; i++){
   for(int j = i; j > 0; j--){
    if(c.compare(datas[j -1],datas[j]) > 0){
     super.swap(datas, j-1, j);
    }
   }
  }
 }

 public static void main(String [] args){
  Insert insert = new Insert();
  Double [] doubles = {1.0, 0.3, 3.4, -0.3, 3.0,3.0, 0.34};
  
  insert.sort(doubles);
  
  System.out.println(Arrays.toString(doubles));
 }
}

public class Client {

 public static void main(String[] args) {
  Person[] persons = { new Person("a", 12), new Person("b", 10),
    new Person("demo", 23), new Person("hello", 22),
    new Person("hello", 32), new Person("xiaomeng", 2) };
  
  Person [] selectPersons = persons.clone();
  
  Person [] quickPersons = persons.clone();
  
  Person [] quickCustomPersons = persons.clone();
  
  Person [] insertPersons = persons.clone();

  System.out.println("排序前 ......");
  System.out.println(Arrays.toString(persons));
  System.out.println();
  
  System.out.println("冒泡排序后 ......");
  new Bubble().sort(persons);
  System.out.println(Arrays.toString(persons));
  System.out.println();  

  System.out.println("选择排序后 ......");
  new Select().sort(selectPersons);
  System.out.println(Arrays.toString(selectPersons));
  System.out.println();
  
  System.out.println("插入排序后 ......");
  new Insert().sort(insertPersons);
  System.out.println(Arrays.toString(insertPersons));
  System.out.println();
  
  System.out.println("快速排序后 ......");
  new Quick().sort(quickPersons);
  System.out.println(Arrays.toString(quickPersons));
  System.out.println();

  System.out.println("使用快速自定义排序 ......");
  new Quick().sort(quickCustomPersons, new Comparator<Person>() {
   public int compare(Person o1, Person o2) {// 倒叙排列    
    return o1.getAge() > o2.getAge() ? -1 : (o1.getAge() == o2.getAge() ? 0 : 1);
   }
  });

  System.out.println(Arrays.toString(quickCustomPersons));
 }
}

class Person implements Serializable, Comparable<Person> {
 private static final long serialVersionUID = -23536L;
 
 private String name;
 private int age;

 public Person() {
 }

 public Person(String name, int age) {
  this.name = name;
  this.age = age;
 }

 public String getName() {
  return name;
 }

 public void setName(String name) {
  this.name = name;
 }

 public int getAge() {
  return age;
 }

 public void setAge(int age) {
  this.age = age;
 }
 
 // 正序排列
 public int compareTo(Person o) {
  if (o == null)
   return -1;

  return this.getAge() < o.getAge() ? -1 : (this.getAge() == o.getAge() ? 0 : 1);
 }

 public String toString() {
  return "name : " + getName() + " age : " + getAge();
 }
}