当前位置：首页 > news >正文

深圳专门做网站/360渠道推广系统

news 2025/6/30 0:45:13

深圳专门做网站,360渠道推广系统,源代码做网站,有哪些做包装设计网站好些桶排序这里是百度百科桶排序介绍图，排序方法描述就是：对于要排序的目标取值范围在0~n-1的m个数，实例说明，排序3,5,6,1,2,4,3这7个数字，取值在0~9之间； 首先建立10个桶子，编号分别为0、1、2………

桶排序

在这里插入图片描述
这里是百度百科桶排序介绍图，排序方法描述就是：对于要排序的目标取值范围在0~n-1的m个数，实例说明，排序3,5,6,1,2,4,3这7个数字，取值在0~9之间；

首先建立10个桶子，编号分别为0、1、2……9，
按照这7个数字，把他们分别放到相应编号的桶子中
从桶子中按顺序收集数据

注明：源数据为按链表排列，每个桶子也是一个链表。
代码如下：


template<class T>
void chain<T>::binSort(int range)
{// Sort the nodes in the chain.// create and initialize the binschainNode<T> **bottom, **top;bottom = new chainNode<T>* [range + 1];top = new chainNode<T>* [range + 1];for (int b = 0; b <= range; b++)bottom[b] = NULL;// 把节点放到箱子中// 箱排序是每个箱子往头结点插入for (; firstNode != NULL; firstNode = firstNode->next){// add firstNode to proper binint theBin = firstNode->element; // type conversion to intif (bottom[theBin] == NULL) // 箱子是空的，直接把插入节点设为头结点bottom[theBin] = top[theBin] = firstNode;else{// bin not emptytop[theBin]->next = firstNode;top[theBin] = firstNode;}}// collect from bins into sorted chain// 把箱子中的节点收集到排序的链表中chainNode<T> *y = NULL;for (int theBin = 0; theBin <= range; theBin++)if (bottom[theBin] != NULL){// bin not emptyif (y == NULL) // first nonempty binfirstNode = bottom[theBin];else // not first nonempty biny->next = bottom[theBin];y = top[theBin];}if (y != NULL)y->next = NULL;//把用来排序的箱子空间释放delete [] bottom;delete [] top;
}

基数排序

基数排序是桶排序的升级版
基数排序是多个桶排序，比如二位数的基数排序，取模10，然后对于个位、十位，有0~9共10个箱子，先按照各位排序，把整个数字放到桶子中，放到桶子中相应位置的编号为该数字的个位数，放进去之后，进行桶排序，结果是一个个位有序，而十位无序的表，然后把该表按照十位为其编号放到桶子中，桶排序，进行收集，之后的结果就是整体有序的数字了。

计算执行步数的话，例如对于取值在0~10^6的1000个数字，如果按照模1000的基数排序，一共需要两次桶排序，每次桶排序共需要1000+1000+1000=3000个步骤，共2*3000=6000
为什么是3000？
1000个桶子初始化->分配1000个整数->从1000个桶子中收集；
因此，如果按照模100的计数排序共需要3*(100+1000+100)=3600个执行步
把数分解为数字需要出发和取模操作。如果用基数10来分解，那么从最低位到最高位的数字分解式为x%10;(x%100)/10;(x%1000)/100;……

template<class T>
int chain<T>::decompose(int value,int range,int time)
{if(time == 1)return value%range;for(int i = 1; i < time; i++){range *=10;}return (value%range)/(range/10);
}
template<class T>
void chain<T>::binSort(int range)
{for(int time = 1;time < 3; time++){// Sort the nodes in the chain.// create and initialize the binschainNode<T> **bottom, **top;bottom = new chainNode<T>* [range + 1];top = new chainNode<T>* [range + 1];for (int b = 0; b <= range; b++)bottom[b] = NULL;// 把节点放到箱子中// 箱排序是每个箱子往头结点插入for (; firstNode != NULL; firstNode = firstNode->next){// add firstNode to proper binint theBin = decompose(firstNode->element,range,time); // type conversion to intif (bottom[theBin] == NULL) // 箱子是空的，直接把插入节点设为头结点bottom[theBin] = top[theBin] = firstNode;else{// bin not emptytop[theBin]->next = firstNode;top[theBin] = firstNode;}}// collect from bins into sorted chain// 把箱子中的节点收集到排序的链表中chainNode<T> *y = NULL;for (int theBin = 0; theBin <= range; theBin++)if (bottom[theBin] != NULL){// bin not emptyif (y == NULL) // first nonempty binfirstNode = bottom[theBin];else // not first nonempty biny->next = bottom[theBin];y = top[theBin];}if (y != NULL)y->next = NULL;//把用来排序的箱子空间释放delete [] bottom;delete [] top;}
}
template<class T>
void chain<T>::RadixSort(int range)
{// Sort the nodes in the chainbinSort(range);//对个位进行排序
}