Java實作快速排序算法-Quick Sort

算法簡介

快速排序（Quick Sort） 是由冒泡排序改進而得的。在冒泡排序過程中，隻對相鄰的兩個記錄進行比較，是以每次交換兩個相鄰記錄時隻能消除一個逆序。如果能通過兩個（不相鄰）記錄的一次交換直接消除多個逆序，則會大大加快排序的虛度。快速排序方法中的一次交換可以消除多個逆序。

算法步驟

在待排序的n個記錄中任取一個記錄（通常選取第一個記錄）作為樞軸，設其關鍵字為

pivotkey

。經過一趟排序後，把所有關鍵字小于

pivotkey

的記錄交換的前面，把所有大于

pivotkey

的記錄交換到後面，結果将待排序記錄分成兩個子表，最後将樞軸放置在分界處的位置。然後對左右兩個子表重複上述過程，直到每一個子表隻有一個記錄時，排序完成。換句話說，就是每一趟排序都将一條記錄放在了正确的位置上。（正确位置就是完成排序時它所處的位置）

具體步驟

1. 選擇待排序表中第一個記錄作為樞軸，儲存在變量

   pivotkey

   中。附設兩個指針

   low

   和

   high

   ,初始時分别指向表的上界和下界（第一趟時，

   low = 0;high = nums.length

   ）。
2. 從表的最右側位置依次向左側搜尋，當找到第一個值小于

   pivotkey

   的記錄時，将其移動到

   low

   處。具體操作是：當

   low < high

   時，若

   high

   所指記錄大于等于

   pivotkey

   ，則向左移動指針

   high

   ；否則移動該記錄。
3. 然後從表的最左側位置依次向右側搜尋，找到第一個關鍵字大于

   pivotkey

   的記錄，将其移動到

   high

   處。具體操作是：若

   low

   所指記錄的值小于

   pivotkey

   ，則向右移動指針

   low

   ；否則移動該記錄。
4. 重複步驟2和3，直至

   low

   和

   high

   。此時

   low

   和

   high

   的位置即為樞軸在此躺排序的最終位置，原表被分為兩個子表。

代碼實作

public class Sort {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 321, 34, 54, 56, 745, 7546,3,423,463,64,234,143421};
        quickSort(nums);
        for (int n : nums) {
            System.out.println(n);
        }
//        1
//        3
//        34
//        54
//        56
//        64
//        234
//        321
//        423
//        463
//        745
//        7546
//        143421
    }
    public static void quickSort(int[] nums) {
        qSort(nums,0,nums.length - 1);
    }
    public static void qSort(int[] nums,int low,int high) {
        if(low < high) {
            int pivotloc = partition(nums,low,high);
            qSort(nums,low,pivotloc - 1);
            qSort(nums,pivotloc+1,high);
        }

    }
    public static int partition(int[] nums,int low,int high) {
        int pivotkey = nums[low];  //用于比較的樞軸
        while (low < high) {
            while (low < high && nums[high] >= pivotkey) { high --; }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivotkey) { low ++;}
            nums[high] = nums[low];
        }
        nums[low] = pivotkey;
        return low;
    }
}