基数排序在 C++ 中实现

Radix Sort implemented in C++

提问by GobiasKoffi

I am trying to improve my C++ by creating a program that will take a large amount of numbers between 1 and 10^6. The buckets that will store the numbers in each pass is an array of nodes (where node is a struct I created containing a value and a next node attribute).

我试图通过创建一个程序来改进我的 C++，该程序将采用 1 到 10^6 之间的大量数字。将在每次传递中存储数字的桶是一个节点数组（其中 node 是我创建的包含一个值和下一个节点属性的结构）。

After sorting the numbers into buckets according to the least significant value, I have the end of one bucket point to the beginning of another bucket (so that I can quickly get the numbers being stored without disrupting the order). My code has no errors (either compile or runtime), but I've hit a wall regarding how I am going to solve the remaining 6 iterations (since I know the range of numbers).

根据最低有效值将数字分类到桶中后，我将一个桶的末尾指向另一个桶的开头（以便我可以快速获取存储的数字而不会破坏顺序）。我的代码没有错误（编译或运行时），但我在如何解决剩余的 6 次迭代方面遇到了困难（因为我知道数字的范围）。

The problem that I'm having is that initially the numbers were supplied to the radixSort function in the form of a int array. After the first iteration of the sorting, the numbers are now stored in the array of structs. Is there any way that I could rework my code so that I have just one for loop for the 7 iterations, or will I need one for loop that will run once, and another loop below it that will run 6 times before returning the completely sorted list?

我遇到的问题是最初将数字以 int 数组的形式提供给 radixSort 函数。在排序的第一次迭代之后，数字现在存储在结构数组中。有什么方法可以让我重新编写代码，以便在 7 次迭代中只有一个 for 循环，或者我是否需要一个将运行一次的 for 循环，以及它下面的另一个循环将在返回完全排序之前运行 6 次列表？

#include <iostream>
#include <math.h>
using namespace std;

struct node
{
    int value;
    node *next; 
};

//The 10 buckets to store the intermediary results of every sort
node *bucket[10];
//This serves as the array of pointers to the front of every linked list
node *ptr[10];
//This serves as the array of pointer to the end of every linked list
node *end[10];
node *linkedpointer;
node *item;
node *temp;

void append(int value, int n)
{
    node *temp; 
    item=new node;
    item->value=value;
    item->next=NULL;
    end[n]=item;
    if(bucket[n]->next==NULL)
    {
        cout << "Bucket " << n << " is empty" <<endl;
        bucket[n]->next=item;
        ptr[n]=item;
    }
    else
    {
        cout << "Bucket " << n << " is not empty" <<endl;
        temp=bucket[n];
        while(temp->next!=NULL){
            temp=temp->next;
        }
        temp->next=item;
    }
}

bool isBucketEmpty(int n){
    if(bucket[n]->next!=NULL)
        return false;
    else
        return true;
}
//print the contents of all buckets in order
void printBucket(){
    temp=bucket[0]->next;
    int i=0;
    while(i<10){
        if(temp==NULL){
            i++;
            temp=bucket[i]->next;                       
        }
        else break;

    }
    linkedpointer=temp;
    while(temp!=NULL){
        cout << temp->value <<endl;
        temp=temp->next;
    }
}

void radixSort(int *list, int length){
    int i,j,k,l;
    int x;
    for(i=0;i<10;i++){
        bucket[i]=new node;
        ptr[i]=new node;
        ptr[i]->next=NULL;
        end[i]=new node;
    }
    linkedpointer=new node;

    //Perform radix sort
    for(i=0;i<1;i++){
        for(j=0;j<length;j++){          
            x=(int)(*(list+j)/pow(10,i))%10;            
            append(*(list+j),x);
            printBucket(x); 
        }//End of insertion loop
        k=0,l=1;

        //Linking loop: Link end of one linked list to the front of another
        for(j=0;j<9;j++){
            if(isBucketEmpty(k))
                k++;
            if(isBucketEmpty(l) && l!=9)
                l++;
            if(!isBucketEmpty(k) && !isBucketEmpty(l)){
                end[k]->next=ptr[l];
                k++;
                if(l!=9) l++;   
            }

        }//End of linking for loop

        cout << "Print results" <<endl;
        printBucket();

        for(j=0;j<10;j++)
            bucket[i]->next=NULL;                       
        cout << "End of iteration" <<endl;
    }//End of radix sort loop
}

int main(){
    int testcases,i,input;
    cin >> testcases;
    int list[testcases];
    int *ptr=&list[0];
    for(i=0;i<testcases;i++){
        cin>>list[i];
    }

    radixSort(ptr,testcases);
    return 0;
}

回答by suszterpatt

I think you're severely overcomplicating your solution. You can implement radix using the single array received in the input, with the buckets in each step represented by an array of indices that mark the starting index of each bucket in the input array.

我认为您的解决方案过于复杂。您可以使用输入中接收到的单个数组实现基数，每个步骤中的存储桶由一个索引数组表示，这些索引数组标记输入数组中每个存储桶的起始索引。

In fact, you could even do it recursively:

事实上，你甚至可以递归地进行：

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

Of course buckets[i+1] - buckets[i]will cause a buffer overflow when iis 9, but I omitted the extra check or readability's sake; I trust you know how to handle that.

当然buckets[i+1] - buckets[i]在i9时会导致缓冲区溢出，但我省略了额外的检查或可读性；我相信你知道如何处理。

With that, you just have to call radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0)and your array should be sorted.

有了这个，您只需要调用即可radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0)对数组进行排序。

回答by rcgldr

To speed up the process with better memory management, create a matrix for the counts that get converted into indices by making a single pass over the array. Allocate a second temp array the same size as the original array, and radix sort between the two arrays until the array is sorted. If an odd number of radix sort passes is performed, then the temp array will need to be copied back to the original array at the end.

为了通过更好的内存管理来加速该过程，请为通过对数组进行一次传递来转换为索引的计数创建一个矩阵。分配第二个与原始数组大小相同的临时数组，并在两个数组之间进行基数排序，直到数组被排序。如果执行奇数次基数排序，则最后需要将临时数组复制回原始数组。

To further speed up the process, use base 256 instead of base 10 for the radix sort. This only takes 1 scan pass to create the matrix and 4 radix sort passes to do the sort. Example code:

为了进一步加快该过程，请使用基数 256 而不是基数 10 进行基数排序。这只需要 1 次扫描来创建矩阵和 4 次基数排序来完成排序。示例代码：

typedef unsigned int uint32_t;

uint32_t * RadixSort(uint32_t * a, size_t count)
{
size_t mIndex[4][256] = {0};            // count / index matrix
uint32_t * b = new uint32_t [COUNT];    // allocate temp array
size_t i,j,m,n;
uint32_t u;
    for(i = 0; i < count; i++){         // generate histograms
        u = a[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; j++){             // convert to indices
        m = 0;
        for(i = 0; i < 256; i++){
            n = mIndex[j][i];
            mIndex[j][i] = m;
            m += n;
        }       
    }
    for(j = 0; j < 4; j++){             // radix sort
        for(i = 0; i < count; i++){     //  sort by current lsb
            u = a[i];
            m = (size_t)(u>>(j<<3))&0xff;
            b[mIndex[j][m]++] = u;
        }
        std::swap(a, b);                //  swap ptrs
    }
    delete[] b;
    return(a);
}

回答by EvilTeach

Since your values are ints in the range of 0 ... 1,000,000

由于您的值是 0 ... 1,000,000 范围内的整数

You can create a int array of of size 1,000,001, and do the whole thing in two passes

您可以创建一个大小为 1,000,001 的 int 数组，并分两次完成整个操作

Init the second array to all zeros.

将第二个数组初始化为全零。

Make a pass through your input array, and use the value as a subscript to increment the value in the second array.

遍历您的输入数组，并使用该值作为下标来增加第二个数组中的值。

Once you do that then the second pass is easy. walk through the second array, and each element tells you how many times that number appeared in the original array. Use that information to repopulate your input array.

一旦你这样做了，那么第二遍就很容易了。遍历第二个数组，每个元素都会告诉您该数字在原始数组中出现的次数。使用该信息重新填充输入数组。