통 정렬 (Bucketsert) 사상 과 실현

2183 단어 정렬 알고리즘
통 정렬 은 간단 하고 이해 하기 쉬 운 정렬 알고리즘 에 속 하 므 로 이 알고리즘 의 사상 을 소개 한다.
(1) 통 정렬 사상
통 정렬 의 사상 은 먼저 배열 을 한 번 훑 어보 고 배열 에서 가장 큰 요 소 를 찾 아 가장 큰 요 소 를 Max 라 고 가정 하 는 것 이다.그리고 맥 스 + 1 개의 '통' 을 정의 합 니 다. '대기 열' 이나 '창고' 로 정의 할 수 있 습 니 다.그 다음 에 배열 을 한 번 더 옮 겨 다 니 며 요소 값 이 i 인 요 소 를 i 번 째 통 에 넣 습 니 다.마지막 으로 0 번 째 통 부터 옮 겨 다 니 며 통 에 있 는 요 소 를 기 존 배열 에 순서대로 넣 고 맥 스 통 까지 옮 겨 다 닐 때 까지 한다.
이 를 통 해 알 수 있 듯 이 통 정렬 의 목적 은 메모리 공간 을 확대 하 는 대가 로 시간의 복잡 도 를 줄 이 는 것 이다.그러나 만약 에 배열 의 요소 가 매우 적 고 배열 의 중간 값 이 가장 큰 요소 가 매우 클 때 이런 알고리즘 을 사용 하면 시간 복잡 도 를 줄 일 수 없 기 때문에 실제 적 으로 이런 정렬 알고리즘 을 사용 하지 않 는 다.또한 부동 소수점 데이터 에 있어 서 이러한 알고리즘 은 통 의 아래 표 시 를 찾 지 않 는 한 (통 의 아래 표 시 는 정형 이기 때 문) 과 수치 정밀도 의 매 핑 관 계 를 찾 지 않 는 한 매우 적합 하지 않다.통 정렬 을 바탕 으로 이 알고리즘 을 개선 하여 '기수 정렬' 이 생 겼 다. 독자 가 '기수 정렬' 사상 을 알 고 싶 으 면 여 기 를 클릭 할 수 있다.
(2) 통 정렬 의 실현
이번 정렬 알고리즘 은 C + + 모드 프로 그래 밍 으로 이 루어 집 니 다.
#include 
#include 
#include 


using std::cout;
using std::endl;
using std::ostream_iterator;
using std::queue;

template
void PrintArr(T (&arr)[N])
{
    copy(arr,arr+N,ostream_iterator(cout," "));
    cout << endl;
}

template
void BucketSort(T (&arr)[N])
{
    size_t i(0),j(0),max(arr[0]);
    while(i < N) {
        if(arr[i] > max) {
            max = arr[i];
        }
        i++;
    }
    queue buckets[max+1];
    i = 0;
    while(i < N) {
        buckets[arr[i]].push(arr[i]);
        i++;
    }
    i = 0;
    while(i <= max) {
        while(!buckets[i].empty()) {
            arr[j] = buckets[i].front();
            buckets[i].pop();
            j++;
        }
        i++;
    }
}

int main()
{
    int arr[]= {2,1,5,3,2,6,1,1,8,4,7};
    cout << "The init:" << endl;
    PrintArr(arr);
    cout << "The sort:" << endl;
    BucketSort(arr);
    PrintArr(arr);
    cout << "The final:" << endl;
    PrintArr(arr);
}

원본 배열: 2  1   5   3   2   6   1   1   8   4   7
프로그램 실행 결과: 1  1   1   2   2   3   4   5   6   7   8
픽 셀 서브 픽 셀
[210430] Observer 패턴

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage