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

电流输出：

预期输出：

它可以按升序或降序排列。

提前致谢。

标签： c++sortingfractionsrational-number

Answer 1

该operator>方法应该返回布尔值而不是整数。最好写成这样：

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

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

---

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

如果您必须恢复到浮点数进行比较，我不确定您从一开始就拥有理性会获得多少收益。

当然，可能只使用浮点数进行排序是可以的，但在其他任何地方都可以使用有理数。但这是要记住的事情。