经典快排:利用最后一个数作为分界点,小的放左边,大的放右边,可以使用荷兰国旗问题的方法优化
随机快排:产生一个随机位置作为分界点(时间复杂度O(N*logN),额外空间复杂度O(logN))
package 第一节; import java.util.Arrays; public class 快速排序 { public static void quicksort(int[] a) { if(a == null || a.length < 2) { return; } //经典快排和随机快排 //classsort(a,0,a.length-1); randomsort(a,0,a.length-1); } //随机快排 private static void randomsort(int[] a, int left, int right) { if(left < right) { //随机快排就是经典快排的基础上多这一步:产生一个随机位置与最后一个位置的数交换 //从而使时间复杂度理论的长期 期望值是 :O(N*logN) swap(a, right, left+(int)((right-left+1)*Math.random()) ); int par[] = partition(a, left, right, a[right]); randomsort(a, left, par[0]-1); randomsort(a, par[1]+1, right); } } //经典快排 private static void classsort(int[] a, int left, int right) { if(left < right) { int par[] = partition(a,left,right,a[right]); //递归解决(工程上是不允许递归的) classsort(a,left,par[0]-1); classsort(a,par[1]+1,right); } } //荷兰国旗问题的思想(小于放左边,等于放中间,大于放右边) private static int[] partition(int[] a, int left, int right, int num) { int index = left; //当前位置索引 int less = left - 1; //小于区域 int more = right;//大于区域 while(index num) { swap(a,--more,index); }else { index++; } } swap(a, more, right); return new int[]{less+1,more}; } private static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int[] test = testData(10, 100);//产生一个随机数组 System.out.println(Arrays.toString(test));//打印数组 quicksort(test); System.out.println(Arrays.toString(test));//打印数组 } public static int[] testData(int len,int val){ int arr[] = new int[len]; for (int i = 0; i < arr.length; i++) { arr[i] = (int)(val*Math.random()); } return arr; } }