快速排序法

• 快速排序法其實就是對泡沫排序法的升級版，他其實就式將要數據在進行第一輪排序的時候，就直接將數據分割成各自獨立的兩部份，在透過方法對這兩個獨立數據進行排序，達到更有效率的成果。

主要基本觀念

1. 先從陣列中取出一個數作為基準數。
2. 以基準數做分區，將比基準數大的數放到它的右邊，小於或等於它的數全放到它的左邊。
3. 再對左右區間重複第二步，直到各區間只有一個數。

程式範例試做:
import java.util.Arrays;
public class Alex1011_1 {
static int []arr = {43,22,296,34,34,29,109,472,58};
public static void main(String[] args) {
System.out.println("原序列為："+Arrays.toString(arr));
Alex1011_1(arr);
}

public static void Alex1011_1(int [] arr) {
    sort(0,arr.length-1);
    System.out.println("排序後為："+Arrays.toString(arr));
}
public static void sort(int left,int right) {
    if(left < right) {
        int i = left; // 由左至右的索引
        int j = right + 1; // 由右至左的索引
        while(true) {
            while( i+1 < arr.length && arr[++i] < arr[left]); 
            // 向右找, 直到找到比基準值大的數
            while( j-1 >= 0 && arr[--j] > arr[left]); // 向左找, 值到找到比基準值小的數
            if( i >= j) break; // 若i,j重疊或i超過j後則退出循環
            swap(i , j);
        }
        swap(left , j); // 基準點與 j 交換
        sort(left , j - 1); // 遞迴排序基準點左子序列
        sort(j + 1 , right); // 遞迴排序基準點右子序列

    }
}

public static void swap(int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

}

程式執行結果:

原序列為：[43, 22, 296, 34, 34, 29, 109, 472, 58]
排序後為：[22, 29, 34, 34, 43, 58, 109, 296, 472]

時間複雜度

最佳：O(nlogⁿ) log是在次方項喔!
平均：O(nlogⁿ) log是在次方項喔!
最差：O(n⁵/⁴)