计数排序的修改

Question

下面的计数排序根据元素的 ASCII 值对元素进行排序。下面的代码工作正常，但我想做一些 I/O 修改。该代码不接受自定义输入。

我尝试进行一些更改，但出现未定义的行为。我的第一个疑问是为什么我会出现未定义的行为。其次，请向我提供使下面的代码运行符合预期的代码。评论部分是我自己尝试的。我希望它从用户那里获取输入。

#include<bits/stdc++.h>
#include<string.h>

using namespace std;

#define RANGE 255

void countSort(char arr[])      //void countSort(char arr[],int n)
{
    char output[strlen(arr)];   //char output[n];

    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    for(i = 0; arr[i]; i++) {
        count[arr[i]]++;
    }

    for (i = 1; i <= RANGE; ++i) {
        count[i] += count[i-1];
    }

    for (i = 0; arr[i]; ++i) {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }

    for (i = 0; arr[i]; ++i) {
        arr[i] = output[i];
    }
}

// Driver code
int main()
{
    char arr[] = "geeksforgeeks";

    countSort(arr);

    cout<< "Sorted character array is "<<arr;

/*
    int n;
    cin>>n;
    char arr[n];

    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }
    countSort(arr,n);

    for(int i=0;i<n;i++) {
        cout<<endl<<arr[i];
    }
*/
    return 0;
}

Answer 1

我猜 'getting undefined behavior' 你的意思是 分段错误 有时发生。问题出在这一行

for(i = 0; arr[i]; i++)

你应该写成

for(i = 0; i < n; i++)

你可以检查第一种情况在每个循环结束时arr[i]是有时一些奇怪的字符（这个字符不属于输入字符串) 和 count[arr[i]] 对于此字符 returns 负数会在此处产生分段错误

output[count[arr[i]]-1] = arr[i];

Answer 2

所以 OP 问了，如何从用户那里获取输入并对其进行排序。而不是给定字符数组中的预定义字符串。

我会给出答案。但是题目是用C++打的，我转成C++。

顺便说一下。问题中的代码是 GeeksforGeeks and tries to code the so called Counting Sort algorithm in C++ that is described here.

的一对一副本

由于代码取自 GeeksforGeeks，不幸的是，我需要将非常糟糕的 C++ 代码归咎于用户 "rathbhupendra"。真的很抱歉。

代码正在使用：

C-Style 数组
可变长度数组（编译器扩展。不符合 C++）
strlen
内存集
#include<bits/stdc++.h> and #include<string.h>
使用命名空间标准
for 循环中的异常结束条件 for(i = 0; arr[i]; ++i)
char 数组而不是 std::strings
定义数组大小的宏(#define RANGE 255)

所以，没有 C++。

现在，答案。

您需要使用 std::getline.

函数从 std::string 类型的变量中读取用户的字符串

一个std::string可以像字符数组一样使用。没有区别。

请看C++解决方案：

编辑

根据 MichaelDorgan 的评论进行编辑

#include <iostream>
#include <string>
#include <vector>

constexpr size_t AsciiRange = 256;

// Convert signed char to unsigned size_t type.
inline size_t char2sizet(char c) { return static_cast<size_t>(static_cast<unsigned char>(c)); }

void countSort(std::string& stringToSort)      
{
    std::vector<size_t> count(AsciiRange, 0U);

    size_t i { 0U };
    for (i = 0U; i < stringToSort.size(); i++) {
        count[char2sizet(stringToSort[i])]++;
    }

    for (i = 1U; i < AsciiRange; ++i) {
        count[i] += count[i - 1U];
    }

    std::string output(stringToSort);  
    for (i = 0U; i < stringToSort.size(); ++i) {
        output[count[char2sizet(stringToSort[i])] - 1U] = stringToSort[i];
        --count[char2sizet(stringToSort[i])];
    }

    stringToSort = output;
}

int main()
{
    std::cout << "\nPlease enter a string:\n\n";

    // Get the string from the user
    std::string inputString{};
    getline(std::cin, inputString);

    // Sort it by characters
    countSort(inputString);

    // Show result
    std::cout << "\n\n\nString sorted by characters is:\n\n" << inputString << '\n';

    return 0;
}

希望这对您有所帮助。 . .

计数排序的修改

Modification of counting sort

c++

algorithm

counting-sort