使用list實(shí)現(xiàn)了排序的中比較簡(jiǎn)單的插入排序，箱子排序和基數(shù)排序，其中，箱子排序和基樹(shù)排序只能用于數(shù)的排序，所以限制還是蠻大的，箱子排序在實(shí)際使用中基本上不使用，箱子排序是基數(shù)排序的基礎(chǔ)，基數(shù)排序有MSD和LSD，MSD也就是從最高位開(kāi)始向最低位排序，LSD也就是從最低位向最高位排序。
下面附上我的實(shí)現(xiàn)代碼：
//============================================================================
// 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);
/**
* 實(shí)現(xiàn)插入排序，箱子排序和基數(shù)排序
*/
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;
}
/**
* 插入排序
* 假定數(shù)組的第1個(gè)元素是排好序的，則從第2個(gè)元素開(kāi)始
* 與前面的元素進(jìn)行排序，這樣就能夠?qū)崿F(xiàn)排序了
* 例如： 2 1 4 3
* 假定第1個(gè)元素2已排好序了
* 則從第2個(gè)元素1開(kāi)始，向前找，2大于1
* 則將2向后移動(dòng)，最后將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;
}
}
}
//獲得數(shù)組中的最大元素
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;
}
//獲得數(shù)組中的最小元素
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;
}
/**
* 箱子排序
* 箱子排序就是相當(dāng)于桶排序，將每個(gè)不1樣大小
* 的數(shù)放入到代表不同數(shù)字的桶中，最后再將桶中的元素順序輸出
*/
void bulletSort(int test[],int size){
int max = Max(test,size);
int min = Min(test,size);
//暫時(shí)使用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 << " ";
}
}
/**
* 基樹(shù)排序（有MSD和LSD）
* 現(xiàn)在先實(shí)現(xiàn)最簡(jiǎn)單的基數(shù)排序，就是對(duì)數(shù)字只有從小到大排序，沒(méi)有種別之分
* 基數(shù)排序的思想就是：
* 先對(duì)個(gè)位數(shù)字進(jìn)行排序，排序完成以后，統(tǒng)計(jì)成堆
* 接著對(duì)上面排好序的10位數(shù)字進(jìn)行排序，排序完成以后，再進(jìn)行對(duì)
* 排好序的百位數(shù)字排序，1次類(lèi)推
*/
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++;
}
}
}
}
}
/**
* 用于對(duì)a和b交換
*/
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
