Coding Life

快速排序法（Quick Sort）是將一個未排序的陣列分成四個部份

1. 比對值（最左邊或最右邊的值，以下代稱S）
2. 比S小的值
3. 比S大的值
4. 未處理的部份

而處理的步驟為

1. 先選出比對值(S)
2. 將剩下的值分成比S小(I)及比S大(J)兩個部份
3. 將S插入兩個數列中間
4. 再分別依左右兩個數列從步驟一開始做，直至數列中只剩一個值

以圖來看如下

↓

↓

↓

當執行到圖4的時候再把Ｉ及Ｊ視為獨立的陣列回到圖1執行

Main.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class Main {
  public static void main(String[] args) {
    List list = new ArrayList<>();
		
    for(int i=0; i<10; i++){
      list.add(new Random().nextInt(10));
    }
		
    Comparator com = new Comparator() {
      public int compare(Integer num1, Integer num2) {
        return num1 - num2;
      }
    };
		
    new Sort().quickSort(list, com);
    System.out.println(list);
  }
}

Sort.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

import static java.util.Collections.swap;

public class Sort {
  public <T> void quickSort(List<T> list, Comparator<? super T> com){
    this.quickSort(list, 0, list.size()-1, com);
  }
    
  private <T> void quickSort(List<T> list, int left, int right, Comparator<? super T> com){
    if(left < right){
      int i = left;
        for(int j=left; j<right; j++){
    	  if(com.compare(list.get(j), list.get(right)) < 0){
    	    swap(list, i, j);
    	    i++;
    	  }
    	}
    	swap(list, i, right);
      this.quickSort(list, left, i-1, com);
      this.quickSort(list, i+1, right, com);
    }    	
  }
}