STL练习2 实现插入排序，箱子排序和基数排序

#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;
}