时间戳

首页 > 解决方案 > 计数排序的修改

c++ - 计数排序的修改

问题描述

下面的计数排序根据元素的 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;
}

标签： c++algorithmcounting-sort

解决方案

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

我会给出答案。但问题是用 C++ 标记的，我会将其转换为 C++。

顺便一提。问题中的代码是GeeksforGeeks的一对一副本，并尝试在此处描述的 C++ 中编写所谓的计数排序算法。

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

该代码正在使用：

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

所以，没有 C++。

现在，答案。

您需要std::string使用函数在类型变量中从用户那里读取字符串std::getline。

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;
}

希望这可以帮助 。. .

推荐阅读