随机快排

Myth丶恋晨 2024-04-18 23:40 2阅读 0赞

package com.hnist.lzn.Resulbe;
    
    import java.util.Random;
    
    public class RandomQuikSort {
    
        public static void sort(int[] arr){
    
            if(arr == null || arr.length == 0)
                return;
            QuickSort(arr,0,arr.length-1);
        }
    
        public static void QuickSort(int[] arr,int L,int R){
    
            if(L>=R)
                return;
            //随机
            swap(arr,L+(int)(Math.random()*(R-L+1)),R);   // 随机取值
            int[] partition = partion(arr,0,R);
            QuickSort(arr,0,partition[0]-1);
            QuickSort(arr,partition[1]+1,R);
        }
    
        public static int[] partion(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);             //将最后一个换过去
            return new int[]{less+1,more};
        }
    
        public static void swap(int[] arr,int a,int b){
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    
        public static void main(String[] args) {
    
           /* int[] arr = {1,1,1,2,3,7,9,5};
    
            sort(arr);
            for(int i:arr){
                System.out.print(i);
                System.out.print(" ");
            }*/
    
    
        }
    
    }