随机+荷兰国旗优化版快排
思路:
快速排序 time O(NlogN) space : O(logN) * 实现思路: * 经典快排，分区是按照数组的最后一个元素进行分区，而在分区的过程中，每次只能确定一个元素的位置。因此，当出现 极端情况 * [1,2,3,4,5,6] or [9,8,5,3,1] 这种已经排序好的情况，time 为O(N^2) * 而荷兰国旗问题的出现解决了，分区每次只能确定一个数的情况。荷兰问题 每次将数据分为3部分 小于目标值 等于目标值 大于目标值 * 当目标值出现多个的时候，可以将等于目标值的数 全部确定位置，而经典快排无法做到这一点。因此 对于有重复元素的快排 荷兰国旗优化版的快排 * 要比经典快排有一定的优势。 * 虽然 荷兰国旗问题了重复元素的问题，但是，由于 选取分区的target是无法确定的。时间复杂度也是无法去评估的。 * 因此 加入随机选取分区的target值，在概率上解决了 将时间复杂度稳定在O(NlogN) space : O(logN) * 而随机快排的space 是由数据的规模决定的，也就是数据的logn次定位。 * 总结 经典快排 》 荷兰国旗问题优化 》 随机快排、 code package com.ncst.base.one; import java.util.Arrays; /** * @author i * @create 2020/5/8 16:27 * @Description * * 快速排序 time O(NlogN) space : O(logN) * 实现思路: * 经典快排，分区是按照数组的最后一个元素进行分区，而在分区的过程中，每次只能确定一个元素的位置。因此，当出现 极端情况 * [1,2,3,4,5,6] or [9,8,5,3,1] 这种已经排序好的情况，time 为O(N^2) * 而荷兰国旗问题的出现解决了，分区每次只能确定一个数的情况。荷兰问题 每次将数据分为3部分 小于目标值 等于目标值 大于目标值 * 当目标值出现多个的时候，可以将等于目标值的数 全部确定位置，而经典快排无法做到这一点。因此 对于有重复元素的快排 荷兰国旗优化版的快排 * 要比经典快排有一定的优势。 * 虽然 荷兰国旗问题了重复元素的问题，但是，由于 选取分区的target是无法确定的。时间复杂度也是无法去评估的。 * 因此 加入随机选取分区的target值，在概率上解决了 将时间复杂度稳定在O(NlogN) space : O(logN) * 而随机快排的space 是由数据的规模决定的，也就是数据的logn次定位。 * 总结 经典快排 》 荷兰国旗问题优化 》 随机快排、 */ public class QuickSort { public static void sortQuick(int [] arr){ if(arr == null || arr.length < 2){ return; } sortQuick(arr,0,arr.length-1); } private static void sortQuick(int[] arr, int l, int r) { if(l < r){ //随机快排 swap(arr,l+(int)(Math.random()*(r-l+1)),r); int[] partition = partition(arr, l, r); sortQuick(arr,l,partition[0]-1); sortQuick(arr,partition[1]+1,r); } } /*** * 分区操作 * @param arr * @param l * @param r * @return */ public static int [] partition(int [] arr,int l,int r){ int less = l-1; int more = r; while (l<more){ if(arr[l]<arr[r]){ swap(arr,++less,l++); }else if(arr[l] > arr[r]){ swap(arr,--more,l); }else { l++; } } swap(arr,more,r);// note 每次交换最后数组一个元素和重复元素。 return new int [] {less+1,more}; } private static void swap(int[] arr, int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } public static void main(String[] args) { int [] arr = {1,5,6,3,7,4,0}; sortQuick(arr); System.out.println(Arrays.toString(arr)); } }