使用list实现了排序的中比较简单的插入排序，箱子排序和基数排序，其中，箱子排序和基树排序只能用于数的排序，所以限制还是蛮大的，箱子排序在实际使用中基本上不使用，箱子排序是基数排序的基础，基数排序有MSD和LSD，MSD也就是从最高位开始向最低位排序，LSD也就是从最低位向最高位排序。
下面附上我的实现代码：
//============================================================================
// Name : STLPractice2.cpp
// Author : 陈洪波
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <list>
using namespace std;
void selecrSort(int test[],int size);
void bulletSort(int test[],int size);
void radixSort(int test[],int size,int wei);
/**
* 实现插入排序，箱子排序和基数排序
*/
int main() {
int test[]= {2,1,4,3};
//selecrSort(test,4);
// for(int i = 0;i < 4;i++){
// cout << test[i] << " ";
// }
//bulletSort(test,4);
radixSort(test,4,1);
for(int m = 0;m < 4;m++){
cout << test[m] << " ";
}
cout << endl;
return 0;
}
/**
* 插入排序
* 假定数组的第1个元素是排好序的，则从第2个元素开始
* 与前面的元素进行排序，这样就能够实现排序了
* 例如： 2 1 4 3
* 假定第1个元素2已排好序了
* 则从第2个元素1开始，向前找，2大于1
* 则将2向后移动，最后将1插入到2的位置
* 就变成了 1 2 4 3
* 4比2大，则就保持4所在的位置
* 3比4小，则4后移，比2大，则3放在4的位置
* 这样排序就完成了
* 1 2 3 4
*/
void selecrSort(int test[],int size){
if(size == 1)
return;
int i = 1;
for(i = 1;i < size;i++){
if(test[i-1] > test[i]){
int temp = test[i];
int j = i-1;
while(j>=0 && test[j] >= temp){
test[j+1] = test[j];
j--;
}
test[j+1] = temp;
}
}
}
//获得数组中的最大元素
int Max(int test[],int size){
int i = 0;
int max = test[0];
for(i = 1;i < size;i++){
if(test[i] > max)
max = test[i];
}
return max;
}
//获得数组中的最小元素
int Min(int test[],int size){
int i = 0;
int min = test[0];
for(i = 1;i < size;i++){
if(test[i] < min)
min = test[i];
}
return min;
}
/**
* 箱子排序
* 箱子排序就是相当于桶排序，将每个不1样大小
* 的数放入到代表不同数字的桶中，最后再将桶中的元素顺序输出
*/
void bulletSort(int test[],int size){
int max = Max(test,size);
int min = Min(test,size);
//暂时使用List
list<int> *lists = new list<int>[max-min+1]();
int i = 0;
for(i = 0;i < size;i++){
lists[test[i]-min].push_back(test[i]);
}
//输出
for(i = 0;i < max-min+1;i++){
list<int>::iterator it = lists[i].begin();
cout << *it << " ";
}
}
/**
* 基树排序（有MSD和LSD）
* 现在先实现最简单的基数排序，就是对数字只有从小到大排序，没有种别之分
* 基数排序的思想就是：
* 先对个位数字进行排序，排序完成以后，统计成堆
* 接着对上面排好序的10位数字进行排序，排序完成以后，再进行对
* 排好序的百位数字排序，1次类推
*/
void radixSort(int test[],int size,int wei){
int i = 0;
int m = 0;
for(m = 1;m <= wei;m++){
//还是采取list作为桶
list<int> *lists = new list<int>[10];
for(i = 0;i < size;i++){
int temp = test[i];
int loc = 1;
int tt = 1;
for(tt = 1;tt < m;tt++){
loc *= 10;
}
lists[(temp/loc%10)].push_back(test[i]);
}
int j = 0;
for(i = 0;i < 10;i++){
if(lists[i].size() != 0){
list<int>::iterator it = lists[i].begin();
while(it != lists[i].end()){
test[j] = *it;
it++;
j++;
}
}
}
}
}
/**
* 用于对a和b交换
*/
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}