package com.znzz.quicksort;
//快速排序
import java.util.Arrays;
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,3,65,7,4,6,2};
        System.out.println(Arrays.toString(arr));
       long start =  System.currentTimeMillis(); //獲取系統(tǒng)當(dāng)前時(shí)間（ms）
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(System.currentTimeMillis() - start); //計(jì)算程序所用時(shí)間（ms）
    }
    // 定義方法，用來快速排序
    public static  void quickSort(int[] arr, int left, int right){
         //判斷，如果左邊大于右邊，不合法，直接return
        if (left > right){
            return;
        }
        //定義變量保存基準(zhǔn)數(shù)
        int base = arr[left];
        //定義變量i，指向最左邊
         int i = left;
        //定義變量j，指向最右邊
        int j = right;
        //開始檢索
        while (i != j) {
            //由j從右往左檢索。檢索到比基準(zhǔn)數(shù)小的就停下，檢索到比基準(zhǔn)數(shù)小大的就據(jù)徐檢索
            while (arr[j] >= base && i < j) {
                j--;   //表示從右往左移動(dòng)
            }
            //i從左往右檢索
            while (arr[i] <= base && i < j) {
                i++;   //表示從左往右移動(dòng)
            }
            //到這，表示i、j都停下了，代表都找到了符合的元素，開始交換對應(yīng)元素。
            swap(arr, i, j);
        }
               //到這，說明i = j，表示相遇了
               //停止檢索，把基準(zhǔn)數(shù)和相遇位置的數(shù)交換。
               arr[left] = arr[i];
               arr[i] = base;
              //基準(zhǔn)數(shù)在這就歸位了，這樣，左邊的數(shù)都比它小，右邊的數(shù)都比他大
              //現(xiàn)在開始排左邊。
            quickSort(arr, left, i-1);
        //現(xiàn)在開始排右邊。
        quickSort(arr, i+1, right);
    }
    public  static  void swap(int [] arr, int i, int j){
        int temp = arr[i];
           arr[i] = arr[j];
            arr[j] = temp;
   }
}