Viết xô sắp xếp theo C++

Question

Sách tôi đã nói điều này:

a) Đặt mỗi giá trị của mảng một chiều vào một hàng của dãy nhóm dựa trên chữ số của giá trị đó. Ví dụ, 97 được đặt trong hàng 7, 3 được đặt trong hàng 3, và 100 được đặt trong hàng 0. Đây được gọi là "thẻ phân phối".

b) Lặp qua hàng loạt hàng loạt theo hàng và sao chép các giá trị trở lại mảng ban đầu. Đây được gọi là "thu thập mật khẩu". Thứ tự mới của các giá trị trước đó trong mảng một chiều là 100, 3 và 97.

c) Lặp lại quy trình này cho từng vị trí chữ số tiếp theo.

Tôi gặp rất nhiều khó khăn khi cố gắng hiểu và triển khai điều này. Cho đến nay tôi có:

void b_sort(int sarray[], int array_size) { 
    const int max = array_size; 
    for(int i = 0; i < max; ++i) 
     int array[i] = sarray[i]; 

    int bucket[10][max - 1]; 
} 

Tôi đang nghĩ rằng để sắp xếp chúng theo những người thân, hàng chục, hàng trăm, vv, tôi có thể sử dụng này:

for(int i = 0; i < max; ++i) 
    insert = (array[i]/x) % 10; 
    bucket[insert]; 

trong đó x = 1, 10, 100, 1000, vv. Tôi hoàn toàn bị mất về cách viết này ngay bây giờ.

Answer 1

Đây là loại nhóm dựa trên thông tin trong câu hỏi OP.

void b_sort(int sarray[], int array_size) { 
    const int max = array_size; 
    // use bucket[x][max] to hold the current count 
    int bucket[10][max+1]; 
    // init bucket counters 
    for(var x=0;x<10;x++) bucket[x][max] = 0; 
    // main loop for each digit position 
    for(int digit = 1; digit <= 1000000000; digit *= 10) { 
     // array to bucket 
     for(int i = 0; i < max; i++) { 
      // get the digit 0-9 
      int dig = (sarray[i]/digit) % 10; 
      // add to bucket and increment count 
      bucket[dig][bucket[dig][max]++] = sarray[i]; 
     } 
     // bucket to array 
     int idx = 0; 
     for(var x = 0; x < 10; x++) { 
      for(var y = 0; y < bucket[x][max]; y++) { 
       sarray[idx++] = bucket[x][y]; 
      } 
      // reset the internal bucket counters 
      bucket[x][max] = 0; 
     } 
    } 
} 

Ghi chú Sử dụng một mảng 2ngày cho xô lãng phí rất nhiều không gian ... một loạt các hàng đợi/danh sách thường có ý nghĩa hơn.

Tôi thường không lập trình bằng C++ và mã ở trên được viết bên trong trình duyệt web, do đó lỗi cú pháp có thể tồn tại.

Answer 2

Mã sau sử dụng chữ số thập phân cho một loại nhóm (cho BITS_PER_BUCKET=4). Ofcourse nó có nghĩa là để được instructive, không hiệu quả.

#include <assert.h> 
#include <stdio.h> 

#define TEST_COUNT 100 
#define BITS_PER_BUCKET 4 
#define BUCKET_COUNT (1 << BITS_PER_BUCKET) 
#define BUCKET_MASK (BUCKET_COUNT-1) 
#define PASS_COUNT (8*sizeof(int)/BITS_PER_BUCKET) 

int main(int argc, char** argv) { 

    printf("Starting up ..."); 
    assert((PASS_COUNT*BITS_PER_BUCKET) == (8*sizeof(int))); 
    printf("... OK\n"); 

    printf("Creating repeatable very-pseudo random test data ..."); 
    int data[TEST_COUNT]; 
    int x=13; 
    int i; 
    for (i=0;i<TEST_COUNT;i++) { 
    x=(x*x+i*i) % (2*x+i); 
    data[i]=x; 
    } 
    printf("... OK\nData is "); 
    for (i=0;i<TEST_COUNT;i++) printf("%02x, ",data[i]); 
    printf("\n"); 

    printf("Creating bucket arrays ..."); 
    int buckets[BUCKET_COUNT][TEST_COUNT]; 
    int bucketlevel[BUCKET_COUNT]; 
    for (i=0;i<BUCKET_COUNT;i++) bucketlevel[i]=0; 
    printf("... OK\n"); 

    for (i=0;i<PASS_COUNT;i++) { 

    int j,k,l; 

    printf("Running distribution pass #%d/%d ...",i,PASS_COUNT); 
    l=0; 
    for (j=0;j<TEST_COUNT;j++) { 
     k=(data[j]>>(BITS_PER_BUCKET*i)) & BUCKET_MASK; 
     buckets[k][bucketlevel[k]++]=data[j]; 
     l|=k; 
    } 
    printf("... OK\n"); 

    if (!l) { 
     printf("Only zero digits found, sort completed early\n"); 
     break; 
    } 

    printf("Running gathering pass #%d/%d ...",i,PASS_COUNT); 
    l=0; 
    for (j=0;j<BUCKET_COUNT;j++) { 
     for (k=0;k<bucketlevel[j];k++) { 
     data[l++]=buckets[j][k]; 
     } 
     bucketlevel[j]=0; 
    } 
    printf("... OK\nData is "); 
    for (l=0;l<TEST_COUNT;l++) printf("%02x, ",data[l]); 
    printf("\n"); 

    } 
} 

Answer 3

viết lại mã của Louis bằng C++ 11 với hàng STL.

void bucket_sort(vector<int>& arr){ 
    queue<int> buckets[10]; 
    for(int digit = 1; digit <= 1e9; digit *= 10){ 
     for(int elem : arr){ 
      buckets[(elem/digit)%10].push(elem); 
     } 
     int idx = 0; 
     for(queue<int>& bucket : buckets){ 
      while(!bucket.empty()){ 
       arr[idx++] = bucket.front(); 
       bucket.pop(); 
      } 
     } 
    } 
}