基数桶搜索

Question

我一直在研究 Radix 桶排序算法，我从 2 位数字开始，然后逐步增加到更多位。

我将我的循环硬编码为运行 2 次（因为我硬编码的数字中有 2 位数字）并且有一个错误我无法在第二个循环中查明。

在我清除我的数据向量并将值从我的存储桶推送到我的数据向量之间的某个地方出现了问题...有什么想法吗？

该错误仅发生在某些数字输入中...而其他数字输入（如我注释掉的那些）有效。

#include <math.h>
#include <iostream>
#include <vector>

using namespace std;

// test radix_sort
int main() {
    cout << "==================================\n";
    cout << "Radix bucket sort DEBUG ME\n";
    cout << "==================================\n\n";

    int m = 10;
    int n = 1;

    int arr[] = { 17, 45, 75, 90, 02, 24, 26, 06 }; //create data array
    //int arr[] = { 170, 405, 750, 302, 002, 240, 206, 006 }; //create data array
    vector<int> data (arr, arr + sizeof(arr) / sizeof(arr[0]) ); //create data vector
    int elements = data.size();

    //print data vector
    cout << "Original: ";
    for (int i = 0 ; i < elements ; i++){
    cout << data[i] << " ";
    }
    cout << endl;

    vector< vector<int> > vec(10, vector<int>(0));; //create buckets vector

    for (int t = 0 ; t < 2 ; t++){ //hard coded to run 2 times since max 2 digits

        for (int i = 0 ; i < elements ; i++) //radix sort into buckets
        {
            vec[(data[i]%m)/n].push_back(data[i]);
        }
        data.clear(); //clear from data vector

        for (int i = 0 ; i < elements ; i++) //push buckets in order onto data
        {
            for (int j = 0 ; j < vec[i].size() ; j++)
            {
                data.push_back(vec[i][j]); 
            }
        }

        cout << "#" << t+1 << ": ";
        for (int i = 0 ; i < elements ; i++){ //print data vector
            cout << data[i] << " ";
        }
        cout << endl;


        //multiply modulus by 10
        m = m*10;
        n= n*10;

        for(int i = 0 ; i < 10 ; i++){ //clear all the shit from buckets
            vec[i].clear();
        }
    }
    return 0;
}

Answer 1

将值从 vec 移回 data，您需要遍历所有 10 个存储桶，但您只遍历了其中的 8 个：

   for (int i = 0 ; i < elements ; i++) // elements == 8
   {
        for (int j = 0 ; j < vec[i].size() ; j++)
        {
            data.push_back(vec[i][j]); 
        }
    }

这应该是：

   for (int i = 0 ; i < vec.size(); i++) // vec.size() == 10
   {
        for (int j = 0 ; j < vec[i].size() ; j++)
        {
            data.push_back(vec[i][j]); 
        }
    }

基数桶搜索

Radix Bucket Search

c++

sorting

algorithm

radix-sort

bucket-sort