import java.util.Arrays; public class MyTest { public static void main(String[] args) { int[] arr={4,8,6,2,12,85,36,14,25,35,52,200,30,68,98,58}; QuickSortUtils.quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } }
public class QuickSortUtils { public static void quickSort(int[] arr, int start, int end) { if (start < end) { //找到基准数,所在的索引,就会分为左右两区 int index = getIndex(arr, start, end); //递归左区, quickSort(arr, start, index - 1); // 递归右区 quickSort(arr, index + 1, end); } } //挖坑填数 private static int getIndex(int[] arr, int start, int end) { //定义变量,接收传过来的的参数 int i = start; int j = end; //定义一个基准数 // 1. 将基准数挖出形成第一个坑。 int x = arr[i]; //5 // 2. 由后向前找比他小的数,找到后挖出此数填到前一个坑中。 // 5 1 9 1 6 7 2 4 2 8 while (ix) { j--; //找到了比基准数小的这个数的索引 } if (i < j) { arr[i] = arr[j]; i++; //顺便让i递增一下 } //3. 由前向后找比他大或等于的数,找到后也挖出此数填到前一个坑中。 while (i < j && arr[i] <= x) { i++; //找到了比基准数大的这个数的索引 } if (i < j) { arr[j] = arr[i]; j--; //顺便让j递减一下 } } //基准数,填的到最后一个坑中 arr[i] = x; return i; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)