c++ - 如何在 C++ 中对有理数数组进行排序？

Question

我想对整数类型的有理数数组进行排序。我使用了冒泡排序算法。我将分子除以分母，然后根据浮商值比较两个有理数。但是，我没有得到正确的结果。

排序代码:

void sort(rational arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++)
        for (j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
}

交换代码:

void swap(rational &r1, rational &r2) {
       rational temp;
       temp.set(r1.getNum(),r1.getDenom());
       r1.set(r2.getNum(),r2.getDenom());
       r2.set(temp.getNum(),temp.getDenom());
}

比较代码:

int operator>(const rational&r2) const {
        float n1 = (float)this->num/(float)this->denom;
        float n2 = (float)r2.num/(float)r2.denom;

        if(n1>n2) return 1;
        if(n1==n2) return 0;
        if(n1<n2) return -1;
}

主要

    int main(int argc, char** argv) {

    rational *arr;
    int n = 10;
    cout<<"\You may enter upto 10 relational numbers. How many?"<<endl;
    cin>> n;
    arr = new rational[n];

    fillArray(arr,n);
    cout<<"\nBefore sorting Array contains: "<<endl;
    displayArray(arr,n);
    cout<<"\nAfter sorting Array contains: "<<endl;
    sort(arr,n);
    displayArray(arr,n);
    return 0;
}

当前输出:

预期输出:

可以升序也可以降序

提前致谢。

Answer 1

operator> 方法应该返回一个 boolean 而不是一个整数。最好写成这样:

bool operator> (const rational &r2) const {
    return (float)num / denom > (float)r2.num / r2.denom;
}

---

例如，这里有一个显示您当前行为的完整程序:

#include <iostream>

class rational {
    int num, denom;
public:
    void set(int n, int d) { num = n; denom = d; }
    int getNum() { return num; }
    int getDenom() { return denom; }

    int operator>(const rational &r2) const {
        float n1 = (float)num/(float)denom;
        float n2 = (float)r2.num/(float)r2.denom;

        if(n1>n2) return 1;
        if(n1==n2) return 0;
        if(n1<n2) return -1;
    }

};

void swap(rational &r1, rational &r2) {
    rational temp;
    temp.set(r1.getNum(),r1.getDenom());
    r1.set(r2.getNum(),r2.getDenom());
    r2.set(temp.getNum(),temp.getDenom());
}

void sort(rational arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++)
        for (j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
}

void displayArray(const char *desc, rational *arr, size_t sz) {
    std::cout << desc;
    for (size_t idx = 0; idx < sz; ++idx) {
        std::cout << "  " << arr[idx].getNum() << "/" << arr[idx].getDenom();
    }
    std::cout << '\n';
}

如果你编译并运行它，你会看到:

Before:  1/3  2/7  -1/4  3/11  5/8  1/2
 After:  1/2  5/8  3/11  -1/4  2/7  1/3

这与您的输出基本相同。但是，使用我建议的比较运算符会产生输出:

Before:  1/3  2/7  -1/4  3/11  5/8  1/2
 After:  -1/4  3/11  2/7  1/3  1/2  5/8

排序正确，尽管与预期输出的顺序相反。既然你在问题中说“它可以按升序或降序排列”，我认为这不是问题。

---

您还应注意，有理数的范围和/或精度可能与标准浮点值不同。

如果您必须恢复到 float 以进行比较，我不确定您从一开始就使用有理数会得到多少。

当然，可能仅使用 float 进行排序是可以的，但在其他任何地方都使用有理数。但请记住这一点。