按字母顺序排序字符数组，然后按长度排序

Question

>我有一个结构数组，我可以在其中跟踪每个唯一单词在给定文本中出现的次数：

struct List {
char word[20];
int repeat;
};

现在我需要对此进行排序：

as             6
a              1
appetite       1
angry          1
are            2
and            4
...

对此：

a            1
as           6
and          4
are          2
angry        1
appetite     1
...

(按字母顺序，我的意思是仅通过第一个字母( 到目前为止，我已经提出了这个：

for (i = 0; i < length - 1; i++) {
min_pos = i;
for (j = i + 1; j < length; j++) // find min
if (array[j].word[0] < array[min_pos].word[0]) {
min_pos = j;
}
swap = array[min_pos]; // swap
array[min_pos] = array[i];
array[i] = swap;
}

这段代码非常适合按字母顺序排序，但我无法编写正确的代码来按字母顺序和长度排序。

Answer 1

创建一个比较器函数。

将operator<添加到您的List：

bool operator<(const List &lhs) const {
if(word[0] != lhs.word[0]) {
return word[0] < lhs.word[0];
}
return strlen(word) < strlen(lhs.word);
}

现在使用此运算符进行排序，使用您喜欢的任何算法。

Answer 2

其他人指出，有更快、更干净的排序方法。但是，如果您想使用自己的选择排序，就像您编写的那样，那么您只需要对代码进行一些更改。

将"我需要交换"逻辑与交换逻辑本身分开。然后代码变得更加清晰，并且更清楚地在哪里添加额外的检查。

我在这里只复制了内部循环。您需要将现有的内部循环替换为此内部循环。我不清楚为什么你需要swap_pos和min_pos，所以我不理会语义。

for (j = i + 1; j < length; j++) { // find min
// first, determine whether you need to swap
// You want to swap if the first character of the new word is
// smaller, or if the letters are equal and the length is smaller.
bool doSwap = false;
if (array[j].word[0] < array[min_pos].word[0]) {
doSwap = true;
}
else if (array[j].word[0] == array[min_pos].word[0] &&
strlen(array[j].word) < array[min_pos].word) {
doSwap = true;
}
// do the swap if necessary
if (doSwap) {
swap_pos = j;
swap = array[min_pos]; // swap
array[min_pos] = array[i];
array[i] = swap;
}
}

为了更清楚地说明必要的逻辑更改，我有意避免进行重大的样式更改或简单的优化。

Answer 3

您可以将 lambda 传递给sort来执行此操作：

sort(begin(array), end(array), [](const auto& lhs, const auto& rhs){ return *lhs.word < *rhs.word || *lhs.word == *rhs.word && (strlen(lhs.word) < strlen(rhs.word) || strlen(lhs.word) == strlen(rhs.word) && strcmp(lhs.word, rhs.word) < 0); });

现场示例

Answer 4

使用元组词典比较运算符

不编写此条件的一种简单方法是

#include <tuple>

然后可以使用std::tie：

std::tie(array[j].word[0], array[j].repeat) < std::tie(array[min_pos].word[0], array[min_pos].repeat)

这是有效的std::tie因为它创建了对其参数的左值引用元组。(这意味着std::tie需要变量。如果您想比较函数的结果std::make_tuple或std::forward_as_tuple会更好(

std::tuple有运算符

按字典顺序比较 lhs 和 rhs，即比较第一个元素(如果它们是等效的(，则比较第二个元素，如果它们是等效的，则比较第三个元素，依此类推。

而上面的描述也是如何对比价值不止于此的想法。