c++ - 按字母顺序选择排序程序的问题

Question

我遇到了一道涉及选择排序概念的家庭作业问题。我们得到了一个框架代码，我们需要在其中完成 bool compare(...)和 void selectionsort(...)功能，我已经完成了。然后，运行程序应该对 main() 中给出的字符串进行排序按字母顺序排列，并在打印初始字符串后按字母顺序打印它们。然而，我的并没有按字母顺序排序，在尝试更改多项内容后，我一直在寻找原因。

请注意，我唯一可以编辑的是 compare和 selectionsort方法，仅此而已。我们需要使用 compare selectionsort 中的方法(如果第一个字符串在字母表中比另一个字符串出现得早，则返回 true)比较它们的方法，而不是简单的比较< > =声明。

我相信我的问题与此有关 if for 内的声明循环，但我在找出正确的方法时遇到了很多麻烦。任何帮助将不胜感激!

#include<iostream>
using namespace std;

bool compare(char *str1, char *str2, int strLen1, int strLen2) { // complete this method
    int small;
    if(strLen1 > strLen2)
        small = strLen2;
    else
        small = strLen1;

    //compare lexicographic values
    for(int i=0; i<small;i++){
        if(str1[i] < str2[i])
            return true;
        else if (str2[i] < str1[i])
            return false;
    }

    if (strLen1 < strLen2)
        return true;
    else
        return false;
}

void selectionsort(char **strings, int numStrings, int *eachStringLen) { // complete this method
    /* strings = jagged array
    numStrings = numRows
    eachStringLen = numColumnsInEachRow*/

    for(int i=0; i<numStrings-1;i++){
        int minIndex = i;
        if(compare(strings[i], strings[i+1], eachStringLen[i], eachStringLen[i+1]) == false){
        for(int j=i+1;j<numStrings;j++){
            if(strings[j]<strings[minIndex])
                minIndex = j;
        }
    }

        //swap strings[minIndex] and strings[i]
        char *tempA = strings[i];
        strings[i] = strings[minIndex];
        strings[minIndex] = tempA;

        int tempB = eachStringLen[i];
        eachStringLen[i] = eachStringLen[minIndex];
        eachStringLen[minIndex] = tempB;

    }//end for i
}//end selectionsort

int main() {
    char str0[] = { 'a', 'b', 'c' };
    char str1[] = { 'x', 'y', 'z', 'w' };
    char str2[] = { 'x', 'y', 'z', 'a', 'b' };
    char str3[] = { 'a', 'b', 'c', 'd', 'x' };
    char str4[] = { 'w', 'x', 'c', 'd', 'x' };
    char str5[] = { 'a', 'b', 'c', 'x', 'y' };
    char str6[] = { 'a', 'a', 'c' };
    char str7[] = { 'w', 'x', 'c', 'd', 'x' };
    char str8[] = { 'a', 'b', 'c', 'x'};
    char *strings[] = { str0, str1, str2, str3, str4, str5, str6, str7, str8 };
    int eachStringLength[] = { sizeof(str0) / sizeof(char), sizeof(str1)
            / sizeof(char), sizeof(str2) / sizeof(char), sizeof(str3)
            / sizeof(char), sizeof(str4) / sizeof(char), sizeof(str5)
            / sizeof(char), sizeof(str6) / sizeof(char), sizeof(str7)
            / sizeof(char), sizeof(str8)
            / sizeof(char) };
    int numStrings = 9;
    cout << "*** Original Strings ***" << endl;
    for (int i = 0; i < numStrings; i++) {
        for (int j = 0; j < eachStringLength[i]; j++) {
            cout << strings[i][j];
        }
        cout << endl;
    }
    selectionsort(strings, numStrings, eachStringLength);
    cout << endl << "*** Sorted Strings ***" << endl;
    for (int i = 0; i < numStrings; i++) {
        for (int j = 0; j < eachStringLength[i]; j++) {
            cout << strings[i][j];
        }
        cout << endl;
    }
}

Answer 1

您的排序逻辑略有偏差。您需要两个循环作为 selection sort是 O(N^2)，并且 no comparison sort can be faster than O(NlogN) .

外循环应该遍历每个索引 i。内循环应该找到 i 到 N 范围内的最小元素，并将它与 i 处的元素交换。

我还建议您使用 std::swap使您的代码更具可读性。

因此，您的代码的主体应如下所示:

for(int i=0; i<numStrings;++i){
    int minIndex = i;
    for(int j=i+1;j<numStrings;++j){
        if(compare(strings[j], strings[minIndex], eachStringLen[j], eachStringLen[minIndex])){
            minIndex = j;
        }
    }

    std::swap(strings[i], strings[minIndex]);
    std::swap(eachStringLen[i], eachStringLen[minIndex]);
}//end for i

请注意，您可以编写外部循环以继续 i<numStrings而不是 i<numStrings-1因为最后一个元素必然会与自身交换。但是两个退出条件都可以。

输出是:

*** Original Strings ***
abc
xyzw
xyzab
abcdx
wxcdx
abcxy
aac
wxcdx
abcx

*** Sorted Strings ***
aac
abc
abcdx
abcx
abcxy
wxcdx
wxcdx
xyzab
xyzw