c++ - 使用带有插入排序的结构

Question

我在插入排序时遇到了一些问题，从结构中传递数据。它返回错误:|98|无法在赋值中将“store”转换为“int”。

struct store{
    char tag[5];
    int cost;
    long int volume;
};


void costSort(store storedEntries[], int count);
void volumeSort(store storedEntries[], int count);

int main(){

    store record[100];
    ifstream fin;
    char choice;
    int count = 0;

    fin.open("stockdata.txt");

    //file read in
    if(fin.good())
    {
        while(!fin.eof())
        {
            fin >> record[count].tag;
            fin >> record[count].cost;
            fin >> record[count].volume;
            count++;
        }
    count--;
    }


    cout << "Main Menu:" << endl;
    cout << "c: sort data by Cost\nv: sort data by trade Volume\nq: Quit\nEnter Choice: ";

    cin >> choice;

    switch(choice)
    {
        case 'C':
        case 'c': //costSort(record, count);
            break;
        case 'V':
        case 'v': volumeSort(record, count);
            break;
        case 'q':
        case 'Q': return 0;
            break;
    }
   return 0;
}

void volumeSort(store record[], int count)
{
    int p = 0, item = 0;

    for(int i=1; i<count; i++){
    cout << "test";
        item = record[i];
        p = (i - 1);
        while(p>=0 && item < record[p]){
            record[p+1] = record[p];
            p--;
        }
        record[p+1] = item;
        cout << record[i].tag << " " << record[i].volume << endl;
    }

}

插入排序在void volumeSort()函数中。任何建议将不胜感激，到目前为止我还没有遇到任何问题:S

Answer 1

您正在比较不相似的类型，但没有提供运算符来支持比较(如果正确完成，则不需要)。当前，您正在将 int 与 store 进行比较。您应该比较的是两个存储对象的两个 volume 成员。

一个可能更接近您想要的简单循环是这样的:

// note: count is size_t, an unsigned magnitude. only used signed
//  integer types where it makes sense a negative integer will be
//  plausible input.
void volumeSort(store record[], size_t count)
{
    for(size_t i=1; i<count; ++i)
    {
        // compare current element to one below us, swapping if needed
        // and stopping as soon as we reach an equal or lesser record
        size_t j=i;
        while(j>0 && record[j].volume < record[j-1].volume)
        {
            std::swap(record[j-1], record[j]);
            --j;
        }
    }
}

或类似的东西。注意比较:

record[j].volume < record[j-1].volume

在 while 条件下。苹果对苹果...

---

对于一个有趣的 insertion_sort，它利用了标准库的两个出色特性，std::upper_bound 和 std::rotate，一个相当可以创建函数的密集版本，看起来像这样:

void insertion_sort(store record[], size_t len)
{
    for (auto it = record; it != record+len; ++it)
    {
        std::rotate(std::upper_bound(record, it, *it,
            [](const store& lhs, const store& rhs) { return lhs.volume < rhs.volume; }),
            it, std::next(it));
    }
}

这比乍看起来要高效得多，因为使用 std::upper_bound 在 O(logN) 中完成了对前景元素的正确放置的搜索。然后 std::rotate 打开元素所在的孔并将其交换到位。

只是一些值得思考的东西。再加上将通过补救优化内联的比较器，它比您最初想象的要强大得多。仍然不像 std::sort 那样出色，通常高度利用多种算法进行优化，但仍然是很好的大脑食物。

祝你好运。