常见的五类排序算法图解和实现（多关键字排序：基数排序以及各个排序算法的总结）

  1 //链式队列的节点结构，模拟桶
  2 struct Node
  3 {
  4     int data;//数据域
  5     Node *next;//指针域
  6 };
  7 
  8 //定义程序所需的特殊队列
  9 class Queue
 10 {
 11 private:
 12     Node *front;//链式对列的头指针
 13     Node *rear;//链队的尾指针
 14     
 15 public:
 16     //构造函数，初始化队列（带头结点的链式队列）
 17     Queue()
 18     {
 19         //开始先构造一个空结点，没有数据元素存储
 20         Node *p = new Node;
 21         p->data = NULL;
 22         p->next = NULL;
 23         //开始是空链队，首尾指针分别去指向队头结点
 24         front = p;
 25         rear = p;
 26     }
 27     //析构函数，销毁链队的结点占据的内存
 28     ~Queue()
 29     {
 30         //标记指针
 31         Node *p = front;
 32         //辅助的标记指针，作用是删除结点
 33         Node *q;
 34         //循环遍历整个队列，直到标记指针 p 为 null
 35         while (p != NULL)
 36         {
 37             //比较常见的删除结点内存的写法
 38             q = p;
 39             //指向队列的下一个结点
 40             p = p->next;
 41             //销毁之
 42             delete q;
 43         }
 44     }
 45     //入队方法，从尾进入，节点不存在，需要自行创建结点的方法
 46     void push(int e)
 47     {
 48         Node *p = new Node;
 49         p->data = e;
 50         //本结点作为了队列的尾结点
 51         p->next = NULL;
 52         //然后连接结点到队尾
 53         rear->next = p;
 54         //最后尾指针指向新的末位结点
 55         rear = p;
 56     }
 57     //入队方法，尾进入，节点原来就存在的方法，不需要再新建结点和存储结点的内容
 58     void push(Node *p)
 59     {
 60         //设置此结点为尾结点
 61         p->next = NULL;
 62         //链接结点
 63         rear->next = p;
 64         //尾指针指向新的尾结点
 65         rear = p;
 66     }
 67     //求数据元素的最大位数的方法，也就是求出需要分配和收集的次数
 68     int lengthData()
 69     {
 70         int length = 0;//保存数据元素的 最大位数
 71         int n = 0;   //单个数据元素具有的位数
 72         int d;      //用来存储待比较的数据元素
 73         //指示指针
 74         Node *p = front->next;
 75         //遍历
 76         while (p != NULL)
 77         {
 78             //取出结点的数据，也就是代比较的数据元素
 79             d = p->data;
 80             //如果 d 为正数，很重要的一个技巧，必须是 d 大于 0 的判断
 81             while (d > 0)
 82             {
 83                 //数据位数分离算法
 84                 d /= 10;
 85                 //单个数据元素的位数存储在此
 86                 n++;
 87             }
 88             //沿着链队后移一个元素
 89             p = p->next;
 90             //找出数据元素的最大位数
 91             if (length < n)
 92             {
 93                 length = n;
 94             }
 95             //重新循环往复，n 设置为0
 96             n = 0;
 97         }
 98         //返回最终位数
 99         return length;
100     }
101     //判断队列是否为空
102     bool empty()
103     {
104         //队头指针和队尾指针重合，说明空
105         if (front == rear)
106         {
107             return true;
108         }
109         //否则为不空
110         return false;
111     }
112     //清除队列中的元素
113     void clear()
114     {
115         //直接把头结点之后的链接断开
116         front->next = NULL;
117         //设置尾指针指向头结点即可，回到了构造函数初始化的情景
118         rear = front;
119     }
120     //输出队列中的元素,传入引用参数比较好
121     void print(Queue &que)
122     {
123         //第一个结点是头结点，next 才是第一个存储元素的结点
124         Node *p = que.front->next;
125         //直到尾结点为止
126         while (p != NULL)
127         {
128             cout << p->data << " ";
129             //遍历所有结点
130             p = p->next;
131         }
132     }
133     //基数排序过程
134     void RadixSort(Queue& que)
135     {
136         //声明一个指针数组，该指针数组中存放十个指针，这十个指针需要分别指向十个队列，这是模拟10个桶，因为是0-9的数字，取值范围为10
137         Queue *arr[10];
138         //初始化这十个队列
139         for (int i = 0; i < 10; i++)
140         {
141             //初始化建立头结点
142             arr[i] = new Queue;
143         }
144         //取得待排序数据元素中的最大位数
145         int maxLen = que.lengthData();
146         //因为是 LSD 方式，从后到前，开始比较关键字，然后分配再收集，故开始设置数据分离算法中的除数为 1
147         int d = 1;
148         //将初始队列中的元素分配到十个队列中,maxlen 代表了需要分配和收集的次数
149         for(int i = 0; i < maxLen; i++)
150         {
151             Node *p = que.front->next;
152             //辅助指针 q
153             Node *q;
154             //余数为k，则存储在arr[k]指向的链式队列（桶）中
155             int k;
156             //遍历原始序列
157             while (p != NULL)
158             {
159                 //重要的技巧，数据分离算法过程,最后勿忘模10，取余数，分离出需要的关键字位
160                 k = (p->data / d) % 10;
161                 q = p->next;
162                 //把本结点 p 加入对应的队列中
163                 arr[k]->push(p);
164                 //指针后移，指向下一个结点
165                 p = q;
166             }
167             //清空原始队列
168             que.clear();
169             //分配完毕，马上将十个队列中的数据收集到原始队列中
170             for (int i = 0; i < 10; i++)
171             {
172                 if (!arr[i]->empty())
173                 {
174                     //从首节点开始遍历，不是头结点开始
175                     Node *p = arr[i]->front->next;
176                     //辅助指针 q
177                     Node *q;
178                     while (p != NULL)
179                     {
180                         q = p->next;
181                         //收集到原始队列中，这就是为什么每次分配完毕，需要清除原始队列
182                         que.push(p);
183                         p = q;
184                     }
185                 }
186             }
187             //一趟的分配收集完毕，最后要清空十个队列
188             for (int i = 0; i < 10; i++)
189             {
190                 arr[i]->clear();
191             }
192             //进行下一趟的分配和收集
193             d *= 10;
194         }
195         //输出队列中排好序的元素
196         print(que);
197     }
198 };
199 
200 int main(void)
201 {
202     Queue oldque;
203     int i;
204     
205     cout << "输入 int 类型的待排序的整数序列：输入 ctrl+z 结束输入，再回车即可" << endl;
206     //顺序输入元素
207     while (cin >> i)
208     {
209         oldque.push(i);
210     }
211     //基数排序
212     oldque.RadixSort(oldque);
213 
214     return 0;
215 }