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

使用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;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » STL练习2 实现插入排序,箱子排序和基数排序

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡