// 快速排序方法
public void quickSort(int[] arr,int left,int right){
if (left > right){
return;
}
// 定义变量保存基准数
int base = arr[left];
// 定义变量,指向最左边
int i = left;
// 定义变量,指向最右边
int j = right;
// 当i和j不相遇的时候,在循环中进行检索
while (i != j){
// 由j从右往左检索比基准数小的,如果检索到比基准数小的就停下
// 如果检索大比基准数大的或者相等的,就继续检索
while (arr[j] >= base && i < j){
j--;// j从右向左移动
}
while (arr[i] <= base && i < j){
i++;// i从左向右移动
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 如果上面while循环的条件不成立,会跳出这个循环,往下执行
// 如果以上条件没有成立,也就是i=j,表示i和j相遇了
// 如果i和j相遇了,就交换基准数这个元素和相遇位置的元素
// 相遇位置的值赋给基准值
arr[left] = arr[i];
// 把基准值赋给相遇位置的值
arr[i] = base;
// 第一轮排完后,左边的数字都比基准数小,右边的都比基准数大,分别排左边的和右边的
// 排左边
quickSort(arr, left, i-1);
// 排右边
quickSort(arr, j+1, right);
}
// 测试方法
public class Test01 {
public static void main(String[] args) {
// 引入随机数组
RandomArray ra = new RandomArray();
int[] arr = ra.randomArray(100000);
QuickSort qs = new QuickSort();
BubbleSort bs = new BubbleSort();
long start = System.currentTimeMillis();
qs.quickSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
long num = end - start;
System.out.println("运行时间:" + num);
}
}
// 引入随机数组方法
public class RandomArray {
public int[] randomArray(int n){
Random rd1 = new Random(System.currentTimeMillis()/100);
int num = rd1.nextInt();
int[] arr = new int[n];
for (int i = num; i < num+n; i++) {
Random rd = new Random(i);
int red = rd.nextInt(n*10);
arr[i-num] = red;
}
return arr;
}
}