一堆n组卡片，每张卡片有三个域：卡片的组号，样式以及面值。对其进行排序------数据结构与算法应用C++描述第三版

#pragma once #ifndef __BINSORT_H #define __BINSORT_H #include <iostream> #include <math.h> #include <string> #include <list> using namespace std; struct card{ // int element[3]; /* int deck; int suit; int face; */ //上面的数组表示的是注释中的三个成员 card(int deck,int suit,int face){ element[0] = deck; element[1] = suit; element[2] = face; } }; void binSort(list<card> &theList,int range,int type){ list<card> *p = new list<card>[range+1]; for(auto it = theList.cbegin();it != theList.cend();it = theList.begin()){ p[it->element[type]].push_back(*it);//这个是根据deck分成了不同的箱子 theList.pop_front();//把头结点抛出来，删掉 } //将各个元素 串起来 for(int i = 0; i <= range;++i){ for(auto it = p[i].begin(); it != p[i].end();it=p[i].begin()){ theList.push_back(*it); p[i].pop_front(); } } delete []p; } #endif

.cpp

#include "binSort.h" #define BUFFSIZE 100 int main() { list<card> theCard; int n,deck,suit,face; cout<<"please input the number of group\n"; cin>>n; cout<<"then input the card\n"; for(int i = 0;i != n;++i){ cin>>deck>>suit>>face; theCard.push_front(card(deck,suit,face)); } cout<<"********************\n"; for(auto it = theCard.begin(); it != theCard.end();it++){ std::cout<<" "<<(*it).element[0]<<" "<<(*it).element[1]<<" "<<(*it).element[2]; cout<<"\n"; } for(int i = 0 ; i != 3; ++i) binSort(theCard,n,2-i); cout<<"********************\n"; for(auto it = theCard.begin(); it != theCard.end();it++){ std::cout<<" "<<(*it).element[0]<<" "<<(*it).element[1]<<" "<<(*it).element[2]; cout<<"\n"; } return 0; }

这个卡片的排序的思想其实就是多次桶排序（箱子排序）。可以这样理解，这里用deck,suit,face分别表示组号，样式以及面值。然后其实就是根据这三个值对输入的卡片进行排序。其实可以把这三个数表示为一个整数的三个不同的部位。deck表示的是百位，suit表示的是十位，face表示的是个位数。所以我们可以按照这个顺序进行三次桶排序。第一次根据个位数(deck)排序，第二次根据十位数（suit)排序，第三次根据百位数(deck）进行排序。 总结：其实无论卡片有多少个域(n个域)，然后只需要进行n次桶排序就好了。