정렬 알고리즘 - 자바 구현 (하) 빠 른 정렬

0. 안내
여기 서 하나의 알고리즘 만 말 하고 빠 른 정렬 을 하 는 이 유 는 정렬 효율 이 같은 O (nlogn) 의 몇 가지 정렬 방법 중에서 효율 이 가장 높 기 때문에 자주 사용 되 기 때문이다.게다가 빠 른 정렬 사상 인 분 치 법 도 실 용적 이어서 각 공장 의 면접 에서 가장 많은 질문 을 받 았 다.
1. 기본 사상:
빠 른 정렬 은 일반적으로 재 귀적 으로 이 루어 진다.그 사고방식 은 다음 과 같다. (1) 적당 한 값 을 선정 하여 '주 원' 또는 '중추' (pivot) 라 고 부른다.(2) 이 값 을 바탕 으로 배열 을 두 개의 부분 집합 으로 나 누고 작은 것 은 왼쪽 에 있 으 며 큰 것 은 오른쪽 에 있다.(3) 두 개의 키 배열 에 대해 상기 과정 을 반복 하고 각 배열 에 하나의 요소 만 있 을 때 까지 한다.(4) 정렬 완료.
빠 른 정렬 이 빠 른 이 유 는 주 원 이 한 번 만 이동 하면 최종 위치 에 놓 이기 때문이다.가장 좋 은 상황: 매번 선택 한 주 원 이 마침 그 가 있어 야 할 위치 에 있 을 때 (왼쪽 은 그 보다 작고 오른쪽 은 그 보다 크다) 이것 은 빠 른 정렬 알고리즘 의 가장 좋 은 상황 이 고 알고리즘 시간 이 복잡 할 때 O(nlogn).최 악의 경우: 구역 을 나 눌 때마다 하위 서열 의 길이 가 1 개 씩 n - 1 로 나타 나 는데 그것 은 정말 최 악이 다.이것 은 반드시 우리 의 표현 식 을 다음 과 같이 만 들 것 이다. T(n) = O(n) + T(1) + T(n-1) = O(n) + T(n-1) 이것 은 정렬 을 삽입 하고 정렬 을 선택 하 는 관계 식 과 똑 같 기 때문에 우리 의 최 악의 상황 은 O(n²) 이다.
2 코드 구현:
세부 적 인 실현 이 좋 고 나 쁨 은 빠 른 정렬 의 효율 에 큰 영향 을 주 므 로 몇 가지 주의해 야 할 점 이 있다.
2.1 주 원 을 어떻게 선택 합 니까?
(1) 고정 기준 수가 배열 이 질서 가 있 으 면 위의 방식 으로 는 매우 좋 지 않다. 매번 구분 할 때마다 정렬 대기 서열 의 길 이 를 1 로 줄 일 수 밖 에 없 기 때문이다.시간 복잡 도 O (n)²)。따라서 첫 번 째 원 소 를 기준 으로 사용 하 는 것 은 매우 나쁘다.
(2) 랜 덤 기준 수 는 상대 적 으로 안전 한 전략 입 니 다. 기준 수의 위치 가 랜 덤 이기 때문에 발생 하 는 분할 도 항상 저질 분할 이 나타 나 지 않 습 니 다. 그러나 random 함수 자체 가 소모 되 기 때문에 이 방법 도 좋 지 않 습 니 다.
(3) 세 개 수의 중위 수 를 선택 하여 무 작위 기준 수 방법 으로 선택 하 는 방식 은 분할 하기 어 려 운 확률 을 줄 였 지만 최 악의 경우 O(n²) 이 어색 한 분 위 기 를 완화 시 키 기 위해 '3 수 취 중' 이라는 기준 수 선택 방식 을 도입 했다.

//   pivot，    
    private static int Median3(int arr[], int left, int right) {
        int center = (left + right) / 2;
        if (arr[left] > arr[center]) {
            swap(arr, left, center);
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right);
        }
        if (arr[center] > arr[right]) {
            swap(arr, center, right);
        }
        //        right-1     ，  right       center，    
        swap(arr, center, right-1);
        
        return arr[right - 1];
    }

    private static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

여기 서 우 리 는 중위 수 를 선택 할 뿐만 아니 라 배열 도 일정한 수정 을 했 습 니 다. pivot 와 배열 의 right - 1 위 를 교환 합 니 다. right 위치의 값 은 앞의 비 교 를 통 해 pivot 보다 클 것 입 니 다. 더 이상 비교 하지 않 아 도 됩 니 다. 우 리 는 정렬 해 야 할 것 은 left + 1 에서 right - 2 위치 까지 의 요소 정렬 입 니 다. 이것 은 효율 을 크게 절약 합 니 다.
2.2 부분 집합 구분 을 어떻게 하 는 지:
부분 집합 구분 을 최적화 하 는 데 다음 과 같은 몇 가지 방법 이 있다. (1) 양쪽 에서 중간 으로 옮 겨 다 니 는 양 방향 구분 방식:

왼쪽 은 left + 1 요소 부터 (주의 + i 이기 때문에 left 부터 가 아니 라 left + 1 부터 시작 합 니 다. left 는 이전 단계 에서 이미 배열 되 었 습 니 다) arr [pivot] 보다 큰 요 소 를 찾 아 멈 추 었 습 니 다.

오른쪽 은 right - 2 요소 부터 arr [pivot] 보다 작은 요 소 를 찾 아 멈 춥 니 다.

i 가 j 보다 작 으 면 두 원소 의 위 치 를 교환한다.

(2) 소수 그룹 효율 최적화:

배열 대기 배열 의 길이 가 크 지 않 으 면 빠 른 정렬 의 효율 이 높 지 않 고 오히려 정렬 을 삽입 하 는 것 이 좋 은 선택 이라는 것 을 잘 알 고 있 습 니 다. 그래서 우 리 는 조건 판단 을 했 습 니 다. 배열 대기 배열 의 길이 가 특정한 값 보다 클 때 빠 른 정렬 을 하고 길 이 는 특정한 값 보다 작 을 때 삽입 정렬 을 사용 합 니 다. 이 값 의 크기 는 확정 되 지 않 고 서로 다른 대기 배열 수 입 니 다.조 는 다르다.

2.3 코드:

    private static void quickSortStadard(int[] array, int N) {
        quickSort(arr, 0, N - 1);
    }
    
    private static void quickSort(int arr[], int left, int right) {
        if(right-left>3) {
        
        int pivot = Median3(arr, left, right);
        int i = left;
        int j = right - 1;
        for (;;) {
            //       ，  arr[i]>arr[pivot]
            while (arr[++i] < pivot) {
            }
            //       ，  arr[j] pivot) {
            }
            if (i < j) {
                swap(arr, i, j);
            } else {
                break;
            }
        }
        //    right-1       i  
        swap(arr, i, right - 1);
        //       
        quickSort(arr, left, i - 1);
        //       
        quickSort(arr, i + 1, right);
        }else {
            insertSort(arr, arr.length);
        }
    }

    public static void insertSort(int[] array, int N) {
        int i, j, temp = 0;
        for (i = 1; i < array.length; i++) {//              
            temp = array[i];//      
            for (j = i; j > 0 && array[j - 1] > temp; j--) {//               ,
                array[j] = array[j - 1]; //               ，         
            }
            array[j] = temp;//               
        }
    }