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

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

 

而處理的步驟為

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

 

以圖來看如下

I、J、未處理                    

I          J         未處理     

I           J               

I           J               

當執行到圖4的時候再把I及J視為獨立的陣列回到圖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);
    }    	
  }
}
arrow
arrow
    全站熱搜

    taurus770423 發表在 痞客邦 留言(0) 人氣()