자바 빠 른 정렬 및 3 방향 빠 른 정렬 실현

빠 른 정렬 사상
배열 의 한 요소 (일반적으로 배열 의 첫 번 째 요소) 를 참조 물 로 선택 하고 배열 의 참조물 보다 작은 요 소 를 배열 왼쪽 에 배열 하 며 참조물 보다 큰 요 소 를 배열 오른쪽 에 배열 합 니 다.
빠 른 정렬 작업 절차

배열 a [N] 의 첫 번 째 요소 a [0] 를 참조물 로 하고 두 개의 지침 i, j 를 각각 배열 아래 에 1 과 N - 1 로 표 시 된 위치

를 가리킨다.

이동 포인터 i, a [i] > a [0]

이동 지침 j, a [j] < a [0]

만족 할 때 까지

a [i] 와 a [j]

교환

만족 조건 을 계속 찾 고 교환 하 는 다음 a [i] 와 a [j], i > = j

a [0] 와 a [j] 를 교환

a [j] (즉 교환 전의 a [0]) 를 분계 점 으로 하여 각각 두 개의 하위 배열 에 대해 상기 절 차 를 재 귀적 으로 호출

한다.
코드 구현

public void quickSort(int[] array, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = divide(array, low, high);//                
    quickSort(array, low, mid-1);//              
    quickSort(array, mid+1, high);
}
public int divide(int[] array, int low, int high) {
    int a = array[low];//         
    int i = low + 1;//   
    int j = high;//   
    while(i <= j) {
        while(array[i] <= a) {//                
            if (i >= j) {return;}//           
            i++;
        }
        while(array[j] > a) {//                
            if (j <= i) {return;}
            j--
        };
        swap(array, i++, j--);//                
    }
    swap(array, low, j);
    return j;//                     
}

3 방향 빠 른 정렬
배경
배열 에 중복 요소 가 대량으로 존재 하면 보통 빠 른 정렬 은 모든 중복 요 소 를 다시 나 누 어 정렬 합 니 다.사실 한 요소 의 위치 가 확정 되면 다른 중복 요소 의 위치 도 확정 되 어야 한다.3 방향 빠 른 정렬 이 이 문 제 를 최적화 시 켰 다.

public void multiQuickSort(int[] array, int low, int high) {
    if(low >= high){
        return;
    }
    int i = array[low];//       ，    ，                  
    int j = i + 1;//         
    int k = high;//         
    while(j <= k) {
        if (a[j] < a[i]) {
            swap(array, i, j);//          ，       
            i++;//                 
            j++;//            
        } else if (a[j] == a[i]) {
            j++;//          
        } else {
            swap(array, j, k);//               
            k--;//  ，            
        }
    }//     ，                   
    multiQuickSort(array, low, i - 1);//                      
    multiQuickSort(array, j, high);
}