欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序

程序员文章站 2023-12-31 20:55:04
...
// 快速排序方法
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; } }

上一篇:

下一篇: