C++ 按字符的ASCII值对字符串进行排序

ASCII值

ASCII（美国标准信息交换代码）是计算机和互联网上最常见的字符编码格式，用于文本数据。在标准的ASCII编码数据中，有256个字母、数字或特殊附加字符和控制码的唯一值。

问题陈述

现在，在这个问题中，我们需要找到按字符的ASCII值升序排列的排序字符串，其中字符串是由用户提供给我们的输入。让我们看看我们应该如何解决这个问题。

让我们通过一些示例来理解这个问题。

输入 − s = "$%7wjk()"

输出 − “$%()7jkw”

解释 − 给定字符串的字符的ASCII值如下所示−

$ -> 36
% -> 37
( -> 40
) -> 41
7 -> 55
j -> 106
k -> 107
w -> 119

因此，按照ASCII代码值的递增顺序，字符串将变为“$%()7jkw”

输入 − s = "#m 0f )nk"

输出 − “ #)0fkmn”

解释 − 给定字符串的字符的ASCII值如下所示 −

(space) -> 32
# -> 35
) -> 41
0 -> 48
f -> 102
k -> 107
m -> 109
n -> 110

因此，按照ASCII码值的递增顺序，字符串将变为“ #)0fkmn”

题目解释

让我们试着理解问题并找到解决办法。我们知道ASCII表中有256个字符，每个字符都有一个唯一的值或位置。因此我们的基本目标是根据需要对字符进行排序。我们可以使用内置的排序函数，通过使用外部函数来实现我们的目标。另一种方法是制作一个频率向量，将每个字符的频率存储在该数组中。使用这个频率向量和ASCII值，我们可以得到我们的新字符串。

解决办法1：使用频率向量

步骤

制作一个大小为256的频率向量，因为ASCII表中的总字符数为256，并将整个向量初始化为零
运行一个循环来存储给定字符串的每个字符的频率
现在定义一个初始为空的输出字符串
运行另一个循环来遍历频率向量，通过将第i个位置的frequency_vector[i]的次数转换为字符串来得到输出字符串
将输出字符串作为我们的最终结果返回

示例

下面是上述方法的C++程序实现：

#include <bits/stdc++.h>
using namespace std;
// Function to Sort the string as per ASCII values of the characters
string Helper(string s){
    // Define the size of the given string
    int size = s.length();
    // Define a frequency vector of size 256, which is the same as the size of the characters as per the ASCII table, and initiate the value of the vector as 0
    vector<int> v(256, 0);
    // Run a loop to count the frequency of each character of the string
    for (int i = 0; i < size; i++) {
        v[s[i]]++;
    }   
    // Declare a string, initially empty, to find the final output
    string ans = "";
    // Run another loop to get the final output in accordance with the ASCII table
    for (int i = 0; i < 256; i++) {
        for (int j = 0; j < v[i]; j++)
        // Typecast the integer value to the character value to include it in the loop
            ans = ans + (char)i;
    }
    // Return the final output
    return ans;
}
int main(){
    // Give input as a string by the user
    string s = "$%7wjk()";
    // Call Helper function to perform the remaining tasks
    cout<< "The sorted string as per ASCII values of the characters is: " << Helper(s);
    return 0;
}

输出

The sorted string as per ASCII values of the characters is: $%()7jkw

上述代码的复杂性

时间复杂度 – O(n); 其中n是字符串的大小。在这里，实际的时间复杂度是O(n * 256)，但我们可以将其当作O(n)，因为256可以被看作常数k，而O(k * n)可以被看作O(n)。
空间复杂度 – O(256); 这里额外占用的空间仅为频率数组的空间，大小为256。

解决办法2 使用内置排序函数的解决方案

步骤

定义一个外部比较函数，在排序函数中使用该函数按照ASCII值对字符进行排序，即返回int类型转换值较小的字符。
现在，在帮助函数中使用内置的排序函数，并使用一个额外的参数，比较函数，以正确获取顺序。
调用帮助函数并获取最终的字符串输出。

示例

#include "bits/stdc++.h"
using namespace std;
// Comparison Function to sort the string as per ASCII values of the characters
bool comparison(char ch1, char ch2){ 
    return int(ch1) <= int(ch2);
}
// Function to sort the string as per ASCII values of the characters
string Helper(string s){
    // Sort the string s with the help of the inbuilt function sort()
    sort(s.begin(), s.end(), comparison);
    // Return the final output string s
    return s;
}
int main(){
    // Give input as a string by the user
    string s = "$%7wjk()";
    // Call Helper function to perform the remaining tasks
    cout<< "The sorted string as per ASCII values of the characters is: " << Helper(s);
    return 0;
}

输出

The sorted string as per ASCII values of the characters is: $%()7jkw

上述代码的复杂性

时间复杂性：O(log(n)); 我们知道内置的排序函数需要O(n * log(n))的时间来执行代码。在这种方法中，我们使用了一个内置的排序函数，通过使用额外的比较函数来根据该函数对字符进行排序。
空间复杂性：O(1); 在上述代码中，我们没有在任何数据结构中存储任何变量。

结论

在这篇文章中，我们通过两种方法解决了按照字符的ASCII值按升序找到排序后的字符串的问题。首先，我们可以创建一个大小为256的频率向量（与ASCII表中的字符数量相同），并存储每个字符的频率，然后通过从后向前遍历来得到所需的字符串。另一种方法可以通过内置的排序函数来实现，通过在排序函数中传递额外的参数。