import java.util.Arrays;

/**

* Description:快速排序

* 过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，

* 则可分别对这两部分记录继续进行排序，以达到整个序列有序。

* Date: 2020-12-26

* Time: 3:56 PM

*/

public class QuickSort {

public static void quickSort(int[] array, int begin, int end) {

if (end <= begin) {

return;

}

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

quickSort(array, begin, pivot - 1);

quickSort(array, pivot + 1, end);

}

static int partition(int[] a, int begin, int end) {

// pivot: 标杆位置，counter: 小于pivot的元素的个数

int pivot = end, counter = begin;

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

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

if (i != counter) {

swap(a, counter, i);

}

counter++;

}

}

swap(a, pivot, counter);

return counter;

}

private static void swap(int[] arr, int a, int b) {

int tmp = arr[a];

arr[a] = arr[b];

arr[b] = tmp;

}

public static void main(String[] args) {

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

System.out.println(Arrays.toString(SortConfig.arr));

}

}