빠 른 배열 의 세 가지 실현 방식.

다음 세 가지 알고리즘 은 모두 하나의 무 작위 수 를 비교 요소 로 삼 았 다.배열 이 비교적 질서 가 있 는 것 을 방지 합 니 다 (예 를 들 어 10 만 개의 숫자 중 수 십 개의 난 서 만 있 는 수). 상황 에서 분할 불 균형 을 초래 하고 O (n ^ 2) 등급 의 정렬 으로 퇴화 하 는 것 을 방지 합 니 다.
이 동시에 다른 최적화 사고 도 있다. 예 를 들 어 비교적 작은 등급 의 배열 로 재 귀 할 때 삽입 순 서 는 빠 른 배열 보다 빠르다.(right - left = = 15) 의 경우 삽입 정렬 로 바 꾸 는 것 을 고려 할 수 있다.
일방 통행 로
간단 하고 O (nlogn) 등급 의 빠 른 정렬 입 니 다.백판 으로 쓰기 에 적합 하 다.
중복 요소 가 많 을 때 좌우 분배 불 균형 문 제 를 일 으 켜 O (n ^ 2) 등급 의 정렬 으로 퇴화 할 수 있 습 니 다.

template 
void quciSort(T arr[], int l, int r);

template 
int __quickSort(T arr[], int l, int r);

template 
void quciSort(T arr[],int n) {
    __quickSort(arr, 0, n-1);
}

template 
void __quickSort(T arr[], int l, int r){

    if (l >= r)
        return;

    swap( arr[l] , arr[rand()%(r-l+1)+l] );

    T v = arr[l];
    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ ) {
        if( arr[i] < v ){
            j ++;
            swap( arr[j] , arr[i] );
        }
    }
    swap( arr[l] , arr[j]);

    __quickSort(arr, l, p-1 );
    __quickSort(arr, p+1, r);
}

2 열 쾌속 열차.
가장 전형 적 인 빠 른 배열 로 대부분의 상황 을 처리 할 수 있다.

template 
void quickSort2(T arr[], int n);
template 
void quickSort2(T arr[], int l, int r);

template 
void quickSort2(T arr[], int n) {
    __quickSort2(arr,0,n-1);
}

template 
void __quickSort2(T arr[], int l, int r) {
    if (l >= r)
        return;

    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];
    int i = l+1, j = r;
    while( true ){
        while( i <= r && arr[i] < v )
            i ++;

        while( j >= l+1 && arr[j] > v )
            j --;

        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }

    swap( arr[l] , arr[j]);
    __quickSort2(arr,l,j-1);
    __quickSort2(arr,j+1,r);
}

3 열 쾌속 열차
쌍 로 보다 빠 른 배열 은 대비 요소 와 같은 상황 을 고려 해 야 한다.완전히 무 작위 적 이 고 left - right 가 큰 경우 에는 쌍 로 보다 잃 어 버 릴 수 있 습 니 다 (판단 이 많 기 때 문 입 니 다).그러나 같은 원소 가 대량으로 있 는 상황 에서 속 도 는 매우 빠르다.
이것 만 보면 돼, 나 도 베 낀 거 야.

template 
void quickSort3Ways(T arr[], int n);

template 
void __quickSort3Ways(T arr[], int l, int r);

template 
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}

template 
void __quickSort3Ways(T arr[], int l, int r){

    if( l >= r )
        return;

    swap( arr[l], arr[rand()%(r-l+1)+l ] );

    T v = arr[l];

    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }

    swap( arr[l] , arr[lt] );

    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}