內(nèi)置類比較

Comparable 接口

Comparable 接口的實現(xiàn)

• 通過實現(xiàn) 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 接口實現(xiàn)原理

• 基本數(shù)據(jù)類型的包裝類：直接比較基本數(shù)據(jù)類型的大小
• 字符：比較Unicode碼之差
• 字符串：
  1. 如果一個字符串以另一個字符串為開始，則返回兩個字符串的長度差
  2. 否則返回第一個不相等的字符的Unicode碼之差
• Date類型：根據(jù)日期的長整型數(shù)比較

compareTo () 方法的使用

• 在排序或比較時通過compareTo函數(shù)的返回值決定順序
  舉例：冒泡排序中compareTo 方法的使用

  /**
  * 需要注意的是這里使用的泛型 T 必須實現(xiàn)接口 Comparable
  * T extends Comparable<T> 等同于 T extends Comparable<? super T>
  * 其含義為 T 是實現(xiàn)了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;
  }
  

  舉例：調(diào)用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接口的實現(xiàn)

• 通過實現(xiàn) java.util.Comparator 接口確中的 compare(T o1, T o2)方法實現(xiàn)對象的比較

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

  舉例：在學(xué)生的個人信息中按照分?jǐn)?shù)對學(xué)生類型進(jìn)行比較

  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() 方法的使用

• 在排序或比較時新建一個比較器，通過比較器調(diào)用compare()方法
  舉例：通過成績對學(xué)生進(jìn)行排序

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

  舉例：調(diào)用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 的區(qū)別

排序算法

這里關(guān)注的僅僅是如何進(jìn)行排序而非比較，所以示例程序中的對象只選用整數(shù)
算法中經(jīng)常會用到 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）是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。

標(biāo)準(zhǔn)冒泡排序

算法原理

• 對數(shù)組進(jìn)行兩層循環(huán)遍歷。讓數(shù)組中較小的關(guān)鍵字能夠較快地移動到數(shù)組的頂部，從而當(dāng)兩層循環(huán)結(jié)束，排序即可完成。

  
  

算法實現(xiàn)

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);
            }
        }
    }
}

改進(jìn)冒泡排序

算法原理

• 標(biāo)準(zhǔn)冒泡排序在數(shù)組已經(jīng)有序后依舊進(jìn)行比較操作（不進(jìn)行交換操作），直至循環(huán)結(jié)束

• 這里使用一個標(biāo)志位，來標(biāo)識當(dāng)前數(shù)組是否已經(jīng)有序。如果無序，則繼續(xù)冒泡排序；如果已經(jīng)有序，則退出排序算法。這樣就可以很好地規(guī)避掉一些不必要的比較操作

  
  

算法實現(xiàn)

void bubbleCoreAdvanced(int[] array) {
    boolean status = true; // 記錄是否發(fā)生交換（發(fā)生為ture，未發(fā)生為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;
            }
        }
    }
}

雙向冒泡排序

算法原理

• 在單向冒泡排序算法中，存在著一個著名的“烏龜問題”，即假設(shè)我們需要將序列A按照升序序列排序。序列中的較小的數(shù)字又大量存在于序列的尾部，這樣會讓小數(shù)字在向前移動得很緩慢。
• 基于冒泡排序的基礎(chǔ)上，無論是從前向后遍歷交換，還是從后向前遍歷交換，對程序的邏輯和性能的代價都是不影響的，故可以讓一部分情況下從前向后遍歷交換，另一部分情況從后向前遍歷交換。

  1. 比較相鄰兩個元素的大小。如果前一個元素比后一個元素大，則兩元素位置交換
  2. 對數(shù)組中所有元素的組合進(jìn)行第1步的比較
  3. 奇數(shù)趟時從左向右進(jìn)行比較和交換
  4. 偶數(shù)趟時從右向左進(jìn)行比較和交換
  5. 當(dāng)從左端開始遍歷的指針與從右端開始遍歷的指針相遇時，排序結(jié)束

算法實現(xiàn)

static void doubleBubbleCore(int[] array){
    int left = 0;
    int right = array.length - 1;
    boolean status = false;// 記錄是否發(fā)生交換（發(fā)生為ture，未發(fā)生為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; //未發(fā)生交換表示排序結(jié)束，退出循環(huán)
        }
    }
}