C++통 정렬 을 위 한 예제 코드

통 정렬:정수 
의 원리
원리 약술:필요 한 배열 의 실제 상황 에 따라 일정한 길이 의 1 차원 배열 을 생 성하 여 배열 의 서로 다른 수치의 중복 횟수 를 통계 하고 통 계 를 완성 한 후에 순서대로 이 수 치 를 반복 출력 한다.
실현 절차:
4.567917.정렬 배열 의 최대 치 와 최소 치 를 확정 합 니 다.4.567918.

통 배열 을 생 성하 고 초기 화 합 니 다

4.567917.정렬 이 필요 한 배열 을 통계 하고 통계 결 과 를 해당 하 는 통 에 넣는다4.567917.순환 출력 통,그리고 원 시퀀스 를 교체 합 니 다아 날로 그 생 성 정수 난수

#include <random>
#include <ctime>
 
//      arr[]      len，  [min, max]        
void getRand(int arr[], int len, int min, int max) {
    std::default_random_engine e;
    e.seed(time(0));
    std::uniform_int_distribution<int> u(min,max);
    for (int i = 0; i < len; i++) arr[i] = u(e);
}

통 정렬 실현

#include <climits>
 
void bucketSort(int arr[], int len) {
    //          
    int max = INT_MIN; int min = INT_MAX;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
 
    //      
    //          0，      1
    int bucketLen = max - min + 1;
    //     
    int bucket[bucketLen];
    for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
 
    //     
    int index = 0;
    for (int i = 0; i < len; i++) {
        index = arr[i] - min;
        bucket[index] += 1;
    }
 
    //      
    int start = 0;
    for (int i = 0; i < bucketLen; i++) {
        for (int j = start; j < start + bucket[i]; j++) {
            arr[j] = min + i;
        }
        start += bucket[i];
    }
}

전체 버 전 실행 가능 프로그램

#include <iostream>
#include <random>
#include <ctime>
#include <climits>
 
//     
const int MAX = 30;
const int LEN = 64;
 
void bucketSort(int arr[], int len);
void getRand(int arr[], int len, int min, int max);
 
int main() {
    int arr[LEN] = {0};
 
    //      
    getRand(arr,LEN,0,MAX);
 
    //      
    std::cout << "Before sorted:" << std::endl;
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "" << std::endl;
 
    //   
    bucketSort(arr,LEN);
 
    //      
    std::cout << "After sorted:" << std::endl;
    for (int i : arr) {
        std::cout << i << " ";
    }
}
 
void getRand(int arr[], int len, int min, int max) {
    std::default_random_engine e;
    e.seed(time(0));
    std::uniform_int_distribution<int> u(min,max);
    for (int i = 0; i < len; i++) arr[i] = u(e);
}
 
void bucketSort(int arr[], int len) {
    //          
    int max = INT_MIN; int min = INT_MAX;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
 
    //      
    //          0，      1
    int bucketLen = max - min + 1;
    //     
    int bucket[bucketLen];
    for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
 
    //     
    int index = 0;
    for (int i = 0; i < len; i++) {
        index = arr[i] - min;
        bucket[index] += 1;
    }
 
    //      
    int start = 0;
    for (int i = 0; i < bucketLen; i++) {
        for (int j = start; j < start + bucket[i]; j++) {
            arr[j] = min + i;
        }
        start += bucket[i];
    }
}

결실 

시간 복잡 도 계산
분석 알고리즘 절차:

배열 의 최대 값 과 최소 값 을 정렬 해 야 합 니 다.-순환 len 회

통 배열 을 생 성하 고 초기 화-순환 bucketLen 회

정렬 이 필요 한 배열 을 통계 한 결과 해당 통 에 넣 고-순환 len 회

순환 출력 통,원 시퀀스 교체-순환 bucketLen+len 회

총 시간 복잡 도 는 O(3*len+2*bucketLen)입 니 다.
P.S.부동 소수점 형의 통 순 서 는 각 통 간 의 간격 이 확정 되 지 않 고 각 통 에 저 장 된 값 의 수량 이 정 해 지지 않 는 등 상황 을 고려 하여 필 자 는 아직 기초 적 인 C++연산 을 통 해 실현 할 수 없다.일부 고급 기능 을 사용 하면 시간 복잡 도가 폭발 할 까 봐 최종 적 으로 잃 어 버 리 지 않 고 다른 유형의 정렬 방법 을 연구 하 는 것 이 더욱 가치 가 있다.큰 놈 이 부동 소수점 통 순 서 를 쓰 면 댓 글 이나 개인 적 인 편 지 를 써 도 됩 니 다.감사합니다!
**참고서:아하!알고리즘
여기 서 C++통 정렬 을 실현 하 는 예제 코드 에 관 한 글 은 여기까지 소개 되 었 습 니 다.더 많은 C+통 정렬 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!