/**
* 所谓快排，即冒泡排序的改进版，每次排序过后都会将原有的数组"切割"成两更个小的"数组"
* 以一个数为基准值，每次排序之后，该基准数的某一半边都应小于该基准数，而另一部分则要大于该基 准数
* 循环往复，最终切割成许多更小的部分，以实现快速排序的目的
*/
public class Test {
public static void main(String[] args) {
Random r = new Random();
long start = System.currentTimeMillis();
int[] arr = new int[100];
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt(100);
}
Test.quickSort(arr, 0, arr.length-1);
long end = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println(end-start);
}
public static void quickSort(int[] arr, int start, int end){
//start和end做为起始参数，不应参与变化
//num做为基准数，每次递归后都以新"数组"的第一个数为准
int num = start;
int left = start;
int right = end;
//防止越界，跳出条件
if (left > right) {
return;
}
while(left != right){
while(arr[num] <= arr[right] && left < right){
right--;
}
while(arr[num] >= arr[left] && left < right){
left++;
}
int container = arr[left];
arr[left] = arr[right];
arr[right] = container;
}
int container = arr[left];
arr[left] = arr[num];
arr[num] = container;
quickSort(arr,left+1,end);
quickSort(arr,start,left-1);
}
}
