C++：使用 LSD 基数排序崩溃的字符串排序

Question

我编写了一些代码，旨在使用基数排序对字符串数组进行排序，从最低有效位开始。此函数假定所有字符串的长度都相同，并且每个字符都是小写字母。

每当我进入为临时数组赋值的循环时，我都会遇到崩溃。你可以在这里看到我的功能：

#ifndef RADIX_H
#define RADIX_H

#include <string>
#include <iostream>
using namespace std;

void lsd_string_radix(string array[], int array_size, int max_chars)
{
    string *temp = new string[array_size];

    for(int i = max_chars - 1; i >= 0; i--)
    {
        int count[26] = {0};

        for(int j = 0; j < array_size; j++)
        {
            count[static_cast<int>(array[j][i]) - 97]++;
        }

        for(int j = 1; j <= 26; j++)
        {
            count[j] += count[j - 1];
        }

        for(int j = 0; j < array_size; j++)
        {
            temp[count[static_cast<int>(array[j][i])]++] = array[j]; // crashes here
        }

        for(int j = 0; j < array_size; j++)
        {
            array[j] = temp[j];
        }
    }
}

#endif

我猜我的逻辑有问题，但我这辈子都想不通。

Answer 1

第二次循环后，count[0] 应为零，第三次循环缺少-97。此示例使用大小为 27 而不是 26 的计数解决了该问题。此示例中的第一个循环使用 -96，因此计数 [0] = 0，计数 [1] = # 个 'a' 的实例，计数 [2] = # 个实例的'b's，...... count[26] = # 'z's 的实例，但它仅在第一个循环中使用。这不是必需的，但是将 'z' 的计数放在那里而不是添加 if 语句以避免将计数存储在 count[26].

更简单

#include<iomanip>
#include<iostream>
#include <string>

using namespace std;

void lsd_string_radix(string array[], int array_size, int max_chars)
{
    string *temp = new string[array_size];

    for(int i = max_chars - 1; i >= 0; i--)
    {
        int count[27] = {0};

        for(int j = 0; j < array_size; j++)
            count[static_cast<int>(array[j][i]) - 96]++;

        for(int j = 2; j < 26; j++)
            count[j] += count[j - 1];

        for(int j = 0; j < array_size; j++)
            temp[count[static_cast<int>(array[j][i]) - 97]++] = array[j];

        for(int j = 0; j < array_size; j++)
            array[j] = temp[j];
    }
}

int main()
{
string a[6] = {"mnop", "ijkl", "efgh", "uvwx", "qrst", "abcd"};
    lsd_string_radix(a, 6, 4);
    for(size_t i = 0; i < 6; i++)
        cout << a[i] << endl;
    return 0;
}

如果count[]的大小是26，第一个循环需要修改：

        for(int j = 0; j < array_size; j++){
            if(array[j][i] == 'z')continue;
            count[static_cast<int>(array[j][i]) - 96]++;
        }

或者修改前两个循环：

        for(int j = 0; j < array_size; j++)
            count[static_cast<int>(array[j][i]) - 97]++;

        int m = 0;
        int n;    
        for(int j = 0; j < 26; j++){
            n = count[j];
            count[j] = m;
            m += n;
        }

C++：使用 LSD 基数排序崩溃的字符串排序

C++: Sorting strings using LSD radix sort crashing

c++

arrays

sorting

string

radix-sort