Java에서 빠른 정렬 구현(코드 예)

퀵 정렬은 파티션 교환 정렬(partition-exchange sort)이라고도 하며, 정렬 알고리즘인 퀵 정렬이라고도 합니다.

(추천 튜토리얼: java 학습 웹사이트)

평균 조건에서 n 항목을 정렬하려면 O(nlog n)(큰 O 표기법) 비교가 필요합니다. 최악의 경우에는 O(n^2) 비교가 필요하지만 이런 상황은 흔하지 않습니다. 실제로 퀵 정렬 O(nlog n)은 내부 루프가 대부분의 아키텍처에서 효율적으로 달성될 수 있기 때문에 다른 알고리즘보다 훨씬 빠른 경우가 많습니다.

퀵 정렬은 분할 정복 전략을 사용하여 시퀀스(목록)를 작은 하위 시퀀스와 큰 하위 시퀀스 두 개로 나눈 다음 두 하위 시퀀스를 재귀적으로 정렬합니다.

단계는 다음과 같습니다.

• 피벗 값 선택: 시퀀스에서 "피벗"이라는 요소를 선택합니다.

• 분할: 기본 값보다 작은 모든 요소는 기본 앞에 배치되고 기본 값보다 큰 모든 요소는 기본 뒤에 배치되도록 시퀀스를 재정렬합니다(기본 값과 동일한 숫자는 어느 쪽에도 갈 수 있음). 옆). 이 구분이 완료되면 기준값의 정렬이 완료됩니다.

• 하위 시퀀스 재귀 정렬: 기준 값보다 작은 요소가 있는 하위 시퀀스와 기준 값보다 큰 요소가 있는 하위 시퀀스를 재귀적으로 정렬합니다.

하위로 회귀하는 판단 조건은 시퀀스의 크기가 0 또는 1이라는 것입니다. 이때 시퀀스는 분명히 순서대로입니다.

(추천 동영상 튜토리얼: java learning)

벤치마크 값을 선택하는 구체적인 방법에는 여러 가지가 있습니다. 이 선택 방법은 정렬 시간 성능에 결정적인 영향을 미칩니다.

코드 구현:

 public class QuickSort {
    public static void main(String[] args) {
        int[] arr = SortUtil.randomArr(6);
        SortUtil.printArr(arr);
//        sort(arr,0,arr.length-1);
        sort1(arr,0,arr.length-1);
//        int[] arr1= netherlands(arr,0,arr.length-1);
//        SortUtil.printArr(arr1);
        SortUtil.printArr(arr);
    }
 
    /**
     * 快排1.0，时间复杂度O（n²），找出以arr[right]为界的中间位置，小于等于的放左边，大于等于的放右边
     * 分为左右2个区域，每个区域重复上面的步骤，直到最后left=right
     * @param arr
     * @param left
     * @param right
     */
    public static void sort(int[] arr,int left,int right){
        if(left>=right){return;}
        int mid = partition(arr,left,right);
        sort(arr,left,mid-1);
        sort(arr,mid+1,right);
    }
 
    /**
     * 快排2.0 以arr[right]作为中间值，最差情况时间复杂度O（n²），平均时间复杂度为 O(n logn) 
     * @param arr
     * @param left
     * @param right
     */
    public static void sort1(int[] arr,int left,int right){
        if(left>=right){return;}
        int[] mid = netherlands(arr,left,right);
        sort1(arr,left,mid[0]-1);
        sort1(arr,mid[1]+1,right);
    }
 
    private static int partition(int[] arr, int left, int right) {
        if (left > right) {
            return -1;
        }
        if (left == right) {
            return left;
        }
        int lessEqual = left - 1;
        int index = left;
 
        while (index < right) {
            // 情况1,当前位置小于等于标记值，当前位置不动，标记右移
            if (arr[index] <= arr[right]) {
                lessEqual++;
                // 扩大小于等于区域
                SortUtil.swap(arr, index, lessEqual);
            }
            index++;
        }
        // 右边界位置和大于区域的起始位置交换
        SortUtil.swap(arr, ++lessEqual, right);
        return lessEqual;
    }
 
    /**
     * 荷兰国旗问题
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int[]  netherlands(int[] arr,int left,int right){
        if(left>right){
            return new int[]{-1,-1};
        }
        if(left==right){
            return new int[]{left,right};
        }
        int lessEqual = left-1;
        int i = left;
        int more = right;
        while (i<more){
            // 1.i位置==arr[right],i++
            if (arr[i]==arr[right]){
                i ++;
            }
            // 2.i位置<arr[right],i位置与小于区域右一个位置交换
            else if (arr[i]<arr[right]){
                SortUtil.swap(arr,++lessEqual,i++);
            }
            // 3.i位置>arr[right],i位置与大于区域左一个位置交换，i不动
            else if(arr[i]>arr[right]){
                SortUtil.swap(arr,i,--more);
            }
        }
        SortUtil.swap(arr,right,more);
        return new int[]{lessEqual+1,more};
    }
 
}

위 내용은 Java에서 빠른 정렬 구현(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!