思路
- 随机找数组中一个数做基准数;
- 颠末一个partition操纵,到达基准数左边的数都比它小,右边的数都比它大。以此固定基准数的位置;
- 基准数左侧部门递归做partition操纵;
- 基准数右侧部门递归做partition操纵;
- 递归的出口是只剩一个元素。
partition
功能:颠末一系列比力交换后,使base基准数左边的数都比它小,右边的数都比它大
流程:
- 规定less下标的左边为小于base的区域,more下标的右边为大于base的区域
- 用index指针遍历元素,从数组的L遍历到R
- 遍历到的数小于base,less右移,less位置和index位置元素交换,index右移
- 遍历到的数便是base index右移
- 遍历到的数大于base,more左移,more位置与index位置元素交换,index不动
代码
- /** * 随机快排 */ public static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int base = arr[new Random().nextInt(arr.length)]; int[] cut = partition(arr, base, left, right); quickSort(arr, left, cut[0]); quickSort(arr, cut[1], right); } /** * partition,即荷兰国旗问题 */ public static int[] partition(int[] arr, int base, int left, int right) { int less = left - 1; int more = right + 1; int index = left; while (index < more) { if (arr[index] < base) { less++; exchange(arr, less, index); index++; } else if (arr[index] == base) { index++; } else { more--; exchange(arr, more, index); } } return new int[]{less, more}; } public static void exchange(int[] arr, int minIndex, int index) { int temp = arr[minIndex]; arr[minIndex] = arr[index]; arr[index] = temp; }
复制代码 来源:https://blog.csdn.net/weixin_44713050/article/details/111992591
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作! |