데이터 구조 - 정렬 - 빠 른 정렬 의 무 작위 선택 기준 법

사상: 기본 적 인 빠 른 정렬 은 첫 번 째 또는 마지막 요 소 를 기준 으로 한다.이렇게 하면 배열 이 질서 가 있 는 상황 에서 매번 구분 할 때마다 최 악의 결 과 를 얻 을 수 있다.비교적 흔히 볼 수 있 는 최적화 방법 은 랜 덤 으로 하나의 요 소 를 기준 으로 선택 하 는 것 이다.이런 상황 에서 최 악의 경 우 는 여전히 O (n2) 이지 만 최 악의 경 우 는 입력 데이터 에 의존 하지 않 고 무 작위 함수 의 수치 가 좋 지 않 기 때문이다.실제로 랜 덤 화 빠 른 정렬 이 이론 최 악의 상황 을 얻 을 가능성 은 1 / (2n) 에 불과 하 다.따라서 랜 덤 화 빠 른 정렬 은 절대 다수의 입력 데이터 가 O (nlogn) 에 이 르 는 기대 시간 에 대한 복잡 도 를 나 타 낼 수 있다.
구현 코드 는 다음 과 같 습 니 다:

class Test{
    /*
       * @Description :        
       * @param array
      * @param low
      * @param high
       * @return :   int
       * @exception :
       * @date :   2019/1/9 11:22
       */
     public static int partition(int [] array,int low,int high){

         int tmp=array[low];
         while(low<high){
             while(low<high && array[high]>tmp){
                 high--;
             }
             if(low>=high){
                 break;
             }else{
                 array[low]=array[high];
             }
             while(low<high&&array[low]<tmp){
                 low++;
             }
             if(low>=high){
                 break;
             }else{
                 array[high]=array[low];
             }
         }
         array[low]=tmp;
         return low;
     }
     public static void swap(int []array ,int low,int rand){
         int tmp=array[low];
         array[low]=array[rand];
         array[rand]=tmp;
     }
     public static void quick(int [] array,int low,int high){
         Random random=new Random();
         int randNum=random.nextInt(high-low)+low+1; //low   high        
         swap(array,low,randNum);
         int par=partition(array,low,high);  //         
         if(par>low+1){
             quick(array,low,par-1);
         }
         if(par<high-1){
             quick(array,par+1,high);
         }
     }
     public static void quickSort(int [] array){ 
         quick(array,0,array.length-1);
     }
     public static void main(String [] args){
         int array []=new int[10000];
         Random random=new Random();
         for(int i=0;i<array.length;i++){
             array[i]=random.nextInt(10000)+1;
         }
         quickSort(array);
     }
    }