内置类比较

Comparable 接口

Comparable 接口的实现

• 通过实现 java.lang.Comparable 接口确定该类对象的排序方式
  Comparable 接口中只有一个方法：

  public interface Comparable<T> {
      public int compareTo(T o);
  }
  

  该方法的返回值定义如下:

  返回值 = 0   表示 this == o
  返回值 > 0   表示 this  > o
  返回值 < 0   表示 this  < o
  

  举例：在Integer包装类中

  public final class Integer extends Number implements Comparable<Integer> {
    ···
    public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
      }
    public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
      }
      ···
  }
  

常见引用类型的 Comparable 接口实现原理

• 基本数据类型的包装类：直接比较基本数据类型的大小
• 字符：比较Unicode码之差
• 字符串：
  1. 如果一个字符串以另一个字符串为开始，则返回两个字符串的长度差
  2. 否则返回第一个不相等的字符的Unicode码之差
• Date类型：根据日期的长整型数比较

compareTo () 方法的使用

• 在排序或比较时通过compareTo函数的返回值决定顺序
  举例：冒泡排序中compareTo 方法的使用

  /**
  * 需要注意的是这里使用的泛型 T 必须实现接口 Comparable
  * T extends Comparable<T> 等同于 T extends Comparable<? super T>
  * 其含义为 T 是实现了Comparable的一个类的子类
  */
  public static <T extends Comparable<T>> void sort(T[] array) {
     for (int i = 0; i < array.length; i++) {
         for (int j = array.length - 2; j >= i; j--) {
             if (array[j].compareTo(array[j + 1]) > 0) {
                 swap(array, j, j + 1);
             }
         }
     }
  }
  public static <T> void swap(T[] array, int a, int b){
     T tmp = array[b];
     array[b] = array[a];
     array[a] = tmp;
  }
  

  举例：调用Collections工具类中提供的sort()方法

  public class Collections {
      ···
      public static <T extends Comparable<? super T>> void sort(List<T> list) {
          list.sort(c);
      }
      ···
  }
  public static void main(String[] args) {
      List<Student> stu = new ArrayList();
      ···
      Collections.sort(stu);
  }
  

Comparator 接口

Comparator接口的实现

• 通过实现 java.util.Comparator 接口确中的 compare(T o1, T o2)方法实现对象的比较

  public interface Comparator<T> {
      public int compare(T o1, T o2);
  }
  

  举例：在学生的个人信息中按照分数对学生类型进行比较

  class Student {
      String name;
      int classNo;
      public int score;
      ···
      public int getScore() {
          return score;
      }
      ···
  }
  class StudentSort implements java.util.Comparator<Student>{
      @Override
      public int compare(Student o1, Student o2) {
          return o1.getScore() - o2.getScore();
      }
  }
  

compare() 方法的使用

• 在排序或比较时新建一个比较器，通过比较器调用compare()方法
  举例：通过成绩对学生进行排序

  public static void SortByScore(Student[] stu){
      StudentSort ss = new StudentSort();
      ···
      if(ss.compare(stu[i], stu[i + 1]) > 0){
          ···
      }
      ···
  }
  

  举例：调用Collections工具类中提供的sort()方法并指定比较器

  public class Collections {
      ···
      public static <T> void sort(List<T> list, Comparator<? super T> c) {
          list.sort(c);
      }
      ···
  }
  public static void main(String[] args) {
      List<Student> stu = new ArrayList();
      ···
      Collections.sort(stu, new StudentSort());
  }
  

Comparable 和 Comparator 的区别

排序算法

这里关注的仅仅是如何进行排序而非比较，所以示例程序中的对象只选用整数
算法中经常会用到 swap() 方法交换两个元素的位置

public static <T> void swap(T[] array, int a, int b){
    T tmp = array[b];
    array[b] = array[a];
    array[a] = tmp;
}

冒泡排序

冒泡排序（Bubble Sort）是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

标准冒泡排序

算法原理

• 对数组进行两层循环遍历。让数组中较小的关键字能够较快地移动到数组的顶部，从而当两层循环结束，排序即可完成。

  
  

算法实现

void bubbleCore(int[] array) {
    int arrayLength = array.length;
    for (int i = 0; i < arrayLength; i++) {
        for (int j = arrayLength - 2; j >= i; j--) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
            }
        }
    }
}

改进冒泡排序

算法原理

• 标准冒泡排序在数组已经有序后依旧进行比较操作（不进行交换操作），直至循环结束

• 这里使用一个标志位，来标识当前数组是否已经有序。如果无序，则继续冒泡排序；如果已经有序，则退出排序算法。这样就可以很好地规避掉一些不必要的比较操作

  
  

算法实现

void bubbleCoreAdvanced(int[] array) {
    boolean status = true; // 记录是否发生交换（发生为ture，未发生为false）
    int arrayLength = array.length;
    for (int i = 0; i < arrayLength && status; i++) {
        status = false;
        for (int j = arrayLength - 2; j >= i; j--) {
            if (array[j] > array[j + 1]) {
                swap(array, j, j + 1);
                status = true;
            }
        }
    }
}

双向冒泡排序

算法原理

• 在单向冒泡排序算法中，存在着一个著名的“乌龟问题”，即假设我们需要将序列A按照升序序列排序。序列中的较小的数字又大量存在于序列的尾部，这样会让小数字在向前移动得很缓慢。
• 基于冒泡排序的基础上，无论是从前向后遍历交换，还是从后向前遍历交换，对程序的逻辑和性能的代价都是不影响的，故可以让一部分情况下从前向后遍历交换，另一部分情况从后向前遍历交换。

  1. 比较相邻两个元素的大小。如果前一个元素比后一个元素大，则两元素位置交换
  2. 对数组中所有元素的组合进行第1步的比较
  3. 奇数趟时从左向右进行比较和交换
  4. 偶数趟时从右向左进行比较和交换
  5. 当从左端开始遍历的指针与从右端开始遍历的指针相遇时，排序结束

算法实现

static void doubleBubbleCore(int[] array){
    int left = 0;
    int right = array.length - 1;
    boolean status = false;// 记录是否发生交换（发生为ture，未发生为false）
    while (left < right){
        for (int i = left; i < right; i++){
            if (array[i] > array[i+1]){
                swap(array, i, i + 1);
                status = true;
            }
        }
        right --;
        for (int i = right-1; i >= left; i--){
            if (array[i] > array[i+1]){
                swap(array, i, i + 1);
                status = true;
            }
        }
        left ++;
        if(!status){
            break; //未发生交换表示排序结束，退出循环
        }
    }
}