箱子排序（每一个箱子也是一个小列表） 1，逐个删除输入链表的节点，把删除节点分配到相应的箱子里 2，把每个箱子中的链表收集并连接起来，使其成为一个有序链表 (即连续删除链表首元素，并将其插入某个箱子的链表首位，然后从最后一个箱子开始，逐个删除每个箱子的首元素，并将其插入一个链表为空的链表首位）
void binSort(chain<studentRecord> &thechain, int range) { //初始化箱子 chain<studentRecord> *bin; bin = new chain<studentRecord>[range + 1]; int theNumberOfThechain = thechain.size();//获取链表长度 for (int i = 0; i < theNumberOfThechain; i++) { studentRecord x = thechain.get(0); thechain.erase(0); bin[x.score].insert(0, x); } for (int j = range; j >= 0; j--) { while (!bin[j].empty()) { studentRecord x = bin[j].get(0); bin[j].erase(0); thechain.insert(0, x); } } delete[] bin; } #include<string> using namespace std; struct studentRecord { int score; string name; studentRecord() {} studentRecord(int score, string name) { this->name = name; this->score = score; } int operator != (const studentRecord& x) const //运算符！=的重载 { return (score != x.score); } operator int() const {return score;}//从studentRecord到int的类型转换 }; ostream &operator<<(ostream& out, const studentRecord& x) { { out << x.score << " " << x.name << endl; return out; } }