package Week08;

import java.util.Arrays;

public class QuickSort {

/*

快排的思想：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。

我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。

经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

*/

public int[] quickSort(int[] arr){

quickSort(arr, 0, arr.length-1);

return arr;

}

private void quickSort(int[] arr, int begin, int end) {

if (begin>=end) return;;

int pivot = partition(arr,begin, end);

quickSort(arr,begin,pivot-1);

quickSort(arr,pivot+1,end);

}

//将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间

private int partition(int[] arr, int begin, int end) {

int pivot = end,count =begin;

for(int i=begin;i<end;i++){

if(arr[i]<arr[pivot]){

swap(arr,i,count++);

}

}

swap(arr,count,end);

return count;

}

private void swap(int[] arr, int i, int j) {

if (i!=j){

// int temp = arr[i];

// arr[i] = arr[j];

// arr[j] = temp;

//only int[] can do this way

arr[i] = (arr[i]+arr[j])-(arr[j]=arr[i]);

}

}

}

class Test3 {

public static void main(String[] args) {

int[] arr = {2,3,1,4};

QuickSort sort = new QuickSort();

int[] ans = sort.quickSort(arr);

System.out.println(Arrays.toString(ans));

}

}