빠른 정렬 파티션 쓰기

버클을 만드는 제목:
169 다수 요소
이때 빠른 정렬을 써서 빠른 정렬을 복습했다.

빨리

빠른 배열 사상은 다음과 같다.

보초병 원소 선택pivot;

pivot보다 작은 원소를 pivot 왼쪽에 놓고 pivot보다 큰 원소를 오른쪽에 놓는다. 이렇게 구분한 후에 pivot는 자신이 최종적으로 있어야 할 위치에 있다

피벗 위치의 왼쪽과 오른쪽에 대해 1, 2의 과정을 차례로 진행한다

그 중에서quickSort는 주된 방법이고 지점이 귀속되는 과정이다. 2단계는 핵심적인partition방법이다. 그는 구분을 해서 매 라운드마다 O(n)의 시간으로 하나의 원소의 위치를 확정했다.
따라서 빠른 정렬의 점근 시간 복잡도는 O(nlogn)이다.
스냅 코드:

    public void quickSort(int[] nums){
        sort(nums, 0, nums.length-1);
    }
	// 
    public void sort(int[] nums, int i, int j){
        if( i >= j )return;// 
        int p = partition(nums, i, j);
        sort(nums, i, p-1);
        sort(nums, p+1, j);
    }
	// 
    public int partition(int[] nums, int i, int j){
        // 
        int pivot = nums[i];
        while( i < j ){
            while( i < j && nums[j] >= pivot ){
                j--;// 
            }
            nums[i] = nums[j];
            while( i < j && nums[i] <= pivot ){
                i++;// >pivot 
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;// pivot 
        return i;
    }

제목

이 제목은 다음과 같다.
크기가 n인 그룹을 지정하여 그 중의 다수 원소를 찾습니다.다수의 원소는 수조에서⌊n/2⌋보다 많이 나타나는 원소를 가리킨다.
너는 수조가 비어 있지 않다고 가정할 수 있으며, 주어진 수조는 항상 다수의 원소가 존재한다.
예 1: 입력: [3, 2, 3] 출력: 3 예 2: 입력: [2, 2, 1, 1, 1, 2, 2] 출력: 2
이 문제의 방법은 해시, 몰 투표 알고리즘으로 정렬할 수도 있다.
정렬의 원인은 다수의 원소의 출현 횟수가⌊n/2⌋보다 많기 때문에,정렬 후에nums에 있다.length/2 위치의 요소가 답입니다.
그리고 모든 정렬을 사용하지 않습니다. 매번partition의 결과는 대응하는 위치입니다. 우리는 이 위치와 필요한 nums만 판단합니다.length/2⌋의 관계, 그리고 어느 반으로sort를 계속 호출할지 결정하면 됩니다.
코드는 다음과 같습니다.

class Solution {
    public int majorityElement(int[] nums) {
        int target = nums.length/2;
        int ans = sort( nums, 0, nums.length-1, target );
        return nums[ans];
    }
    // ， 
    public int sort( int[] nums, int i, int j, int k){
        int pos = partition( nums, i, j );
        if( pos==k )return pos;
        if( pos>k )return sort( nums, i, pos-1, k );
        else return sort( nums, pos+1, j, k );
    }

    // 
    public int partition( int[] nums, int i, int j ){
		//。。。
    }
}

그러나 운행 속도는 매우 느리지만 문제풀이에서도 같은 사고방식으로 하는 것을 보면 빠른 부분의partition 코드가 다르고 시간이 거의 50배 빠르다.
그 파티션 코드는 이렇게 쓰여 있습니다.

    public int partition( int[] nums, int i, int j ){
        int pivot = nums[i];
        int left = i;
        int right = j+1;
        while( true ){
            while( ++left<=j && nums[left]<pivot);
            while( --right>=i && nums[right]>pivot );
            if( left>=right )break;
            int t = nums[right];
            nums[right] = nums[left];
            nums[left] = t;
        }
        nums[i] = nums[right];
        nums[right] = pivot;
        return right;
    }

논리적으로 차이가 없는 것 같지만 교환의 순서가 다르고 따로 뒷처리를 추가했다.
그래서 원인을 분석합니다.

로컬에서 랜덤 수를 생성하고 100-1000000000 수량급의 수조에 대해 각각 두 가지 빠른 정렬 코드를 사용하여 테스트를 실시한 결과 이 두 가지partition 코드를 사용하여 운행하는 시간은 모두 같은 수량급으로 차이가 크지 않다

그리고 변수를 제어하고 증가자감의 접두사 위치를 바꾸었고 미리break의 문장을 바꾸었는데 결과는 여전히 차이가 크지 않았다

마지막으로 이 제목에 부합하기 위해 입력을 수정했는데 절반은 무작위 수, 절반은 고정 값, 즉 중수가 있는 상황을 다시 테스트한 결과 차이가 매우 뚜렷하게 나타났다

코드를 결합하여 두 가지 파티션 방안의 차이점은 각각의 pivot에 대한 구분 처리에 있다.
방법 1

while( i < j && nums[j] >= pivot ){
                j--;
            }

방법 2

while( ++left<=j && nums[left]<pivot);

그리고 나서 내가 뒤져보니 알고리즘 도론에서 이 문제가 발생한 적이 있다. 바로 로무토와 호어의 파티 방법이 다르다는 것이다.
첫 번째는 제가 사용하는 일반적인 방법입니다. 하나, 두 번째는 현재 대부분 사용되고 있는 Hoare의 파티션 방법입니다.첫 번째는 실제로 한 번의 단방향 스캐닝만 사용하고 중복 요소를 뛰어넘으면 중복 요소가 많을 때 구분이 매우 불균형적이다. 이 문제는 바로 중복 요소가 매우 많다.
두 번째 방법은 두 가지 지침을 사용하고 중복 원소를 뛰어넘지 않고 엄격하지 않은 역순으로 교환하면 몇 번 더 원소를 교환할 수 있지만 전체적으로 보면 중복 원소가 많을 때 그는 더욱 고르게 구분할 수 있다. 이렇게 나누면 오히려 시간을 절약할 수 있다.
예:

[5 6 7 5 5 5 7 5 5]

그러면 첫 번째 직접right는 left와 같고 왼쪽은 비어 있고 오른쪽은 원수조로 나누어 5를 제거한다.

[5 | 6 7 5 5 5 7 5 5]

두 번째는 구분이 돼요.

[5 5 5 5 | 5 | 5 7 7 6]

수동으로 이 과정을 시뮬레이션할 수 있다.
이 두 가지 파티션의 방법에 대해 인터넷에서 어떤 사람들이 쓴 것은 완전히 반대이고 분석된 상황도 반대이다. 내가 본 것은 비교적 믿을 만한 것은 이 편이다.
https://blog.csdn.net/u011388550/article/details/51532152