排序算法之快速排序（五）

快速排序：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行。

例如：4，3，1，2，6，5，

1.剛開始定義兩個變量i和j指向數組的首尾，首先将i号下标元素值拿出來當作标記位。從j開始由後向前找到第一個比标記位4小的值放到i好下标位置即圖2，然後i向後移動找到第一個比标記位4大的數放到j号下标，如圖三，重複以上步驟，直到i=j，将标記位4放入i=j号下标，至此完成一趟排序，一趟排序之後所有比4小的都在4的左邊，比4大的都在4的右邊。

2.一趟排序之後結果    1，3，2，4，6，5，将1，3，2分為一組，6，5分為一組，繼續進行快排。

完整的過程：

原數組：4，3，1，2，6，5

一趟後    1，3，2，4，6，5

二趟後    1，2，3，4，5，6

時間複雜度  O(nlogn)   空間複雜度O(1)   不具有穩定性

代碼實作

private static <T extends Comparable<T>>void quickSort(T[] arr, int left, int right) {
        if (left >= right){
            return;
        }
        T temp = arr[left];
        int i = left;
        int j = right;
        while (i<j){
            while (arr[j].compareTo(temp)>0 && i<j){
                j--;
            }
            arr[i] = arr[j];
            while (arr[i].compareTo(temp)<=0 && i<j){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
}