快速排序法(Quick Sort)是將一個未排序的陣列分成四個部份
- 比對值(最左邊或最右邊的值,以下代稱S)
- 比S小的值
- 比S大的值
- 未處理的部份
而處理的步驟為
- 先選出比對值(S)
- 將剩下的值分成比S小(I)及比S大(J)兩個部份
- 將S插入兩個數列中間
- 再分別依左右兩個數列從步驟一開始做,直至數列中只剩一個值
以圖來看如下
I、J、未處理 | S |
↓
I | J | 未處理 | S |
↓
I | J | S |
↓
I | S | 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); } } }
全站熱搜