快排模闆

/**
 * @Author Baker.chen
 * @create 2020/8/13 12:13
 *
 * 快速排序
 */
public class QuickSort {

    public static void sort(int[] arr, int left, int right) {
        // 遞歸結束的條件
        if (left > right) {
            return;
        }
        // 因為left和right後面還需要用到這兩個值，是以不應該用它們來周遊，而是用兩個新的變量i，j
        int i = left;
        int j = right;
        // 将數組的第一個值當做基準值，用一個變量存起來
        int temp = arr[left];
        while (i != j) {
            // 從右往左走，找到第一個小于基準值的下标
            while (arr[j] >= temp && i < j) {
                j--;
            }
            // 将找到的這個小于基準值的的數指派給下标為i的位置，并且i++
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            // 從左往右走，找到第一個大于基準值的下标
            while (arr[i] <= temp && i < j) {
                i++;
            }
            // 将找到的這個大于基準值的的數指派給下标為j的位置，并且j--
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        // 一趟循環結束後，将儲存起來的基準值temp賦給下标為i或者為j的位置
        arr[i] = temp;

        // 遞歸對基準值左右兩邊的資料進行快速排序
        sort(arr,left, i-1);
        sort(arr,i+1, right);
    }

    public static void main(String[] args) {
        int[] arr = {12,15,1,18,2,35,30,11};
        System.out.println(Arrays.toString(arr));
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}