import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public static void main(String[] args) {
/* 递归： 自己调用自己
一直在动，反复的做一件事情
两者是否相遇 ： i == j时 两者相遇 ，基准数归位
while（）*/
int [] arr = new int[1000000];
Random rm = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = rm.nextInt();
}
System.out.println("快拍前");
quickSort(arr,0,arr.length-1);
System.out.println("快拍后");
System.out.println(Arrays.toString(arr));
//System.out.println(Arrays.toString(arr));
}
// 递归 得有出口
private static void quickSort(int[] arr, int left, int right) {
if(left > right){
return ;
}
int i = left;
int j = right;
int baseNum = arr[left];
// 开始移动
// 没有相遇
while( i != j){
// 从右边开始解索，如果这个数 大于基准数的话，移动
while(arr[j] >= baseNum && j > i){
j--;
}
while(arr[i] <= baseNum && i < j){
i++;
}
//两者交换位置
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 一旦出了while循环,表示两者相遇
// 基准数归位 : 相遇的元素 和 第一位基准数交换位置
arr[left]= arr[i];
// 把基准数的值给相遇的数
arr[i] = baseNum;
quickSort(arr,left,i-1);
quickSort(arr,j+1,right);
}
}
 |
|
收藏
淘帖
踩
