转自:http://www.cppblog.com/shongbee2/archive/2009/04/24/80992.html
今天学了基数排序,据说他的时间复杂度也是O(n),他的思路就是:
没有计数排序那么理想,我们的数据都比较集中,都比较大,一般是4,5位。基本没有小的数据。
那我们的处理很简单,你不是没有小的数据嘛。我给一个基数,例如个位,个位都是[0-10)范围内的。先对他进行归类,把小的放上面,大的放下面,然后个位排好了,在来看10位,我们也这样把小的放上面,大的放下面,依次内推,直到最高位排好。那么不就排好了吗?我们只需要做d(基数个数)的循环就可以了。时间复杂度相当于O(d * n) 因为d为常量,例如5位数,d就是5.所以近似为O(n)的时间复杂度。这次自己写个案例:
最初的数据 |
排好个位的数据 |
排好十位的数据 |
排好百位的数据 |
981 |
981 |
725 |
129 |
387 |
753 |
129 |
387 |
753 |
955 |
753 |
456 |
129 |
725 |
955 |
725 |
955 |
456 |
456 |
753 |
725 |
387 |
981 |
955 |
456 |
129 |
387 |
981 |
这里只需循环3次就出结果了。
<!--[if !supportLists]-->3. <!--[endif]-->但是注意,我们必须要把个位排好。但是个位怎么排呢?这个是个问题。书上说的是一叠一叠的怎么合并,我是没有理解的。希望知道的有高手教我一下。
我是用的一个计数排序来排各位的,然后排十位。效率应该也低不到哪里去。呵呵。。
思路就这样咯。奉上源代码:
#include <stdio.h>
#include <stdlib.h>
//计数排序,npRadix为对应的关键字序列,nMax是关键字的范围。npData是具体要
//排的数据,nLen是数据的范围,这里必须注意npIndex和npData对应的下标要一致
//也就是说npIndex[1] 所对应的值为npData[1]
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)
{
//这里就不用说了,计数的排序。不过这里为了是排序稳定
//在标准的方法上做了小修改。
int* pnCount = (int*)malloc(sizeof(int)* nMax); //保存计数的个数
for (int i = 0; i < nMax; ++i)
{
pnCount[i] = 0;
}
for (int i = 0; i < nLen; ++i) //初始化计数个数
{
++pnCount[npIndex[i]];
}
for (int i = 1; i < 10; ++i) //确定不大于该位置的个数。
{
pnCount[i] += pnCount[i - 1];
}
int * pnSort = (int*)malloc(sizeof(int) * nLen); //存放零时的排序结果。
//注意:这里i是从nLen-1到0的顺序排序的,是为了使排序稳定。
for (int i = nLen - 1; i >= 0; --i)
{
--pnCount[npIndex[i]];
pnSort[pnCount[npIndex[i]]] = npData[i];
}
for (int i = 0; i < nLen; ++i) //把排序结构输入到返回的数据中。
{
npData[i] = pnSort[i];
}
free(pnSort); //记得释放资源。
free(pnCount);
return 1;
}
//基数排序
int RadixSort(int* nPData, int nLen)
{
//申请存放基数的空间
int* nDataRadix = (int*)malloc(sizeof(int) * nLen);
int nRadixBase = 1; //初始化倍数基数为1
bool nIsOk = false; //设置完成排序为false
//循环,知道排序完成
while (!nIsOk)
{
nIsOk = true;
nRadixBase *= 10;
for (int i = 0; i < nLen; ++i)
{
nDataRadix[i] = nPData[i] % nRadixBase;
nDataRadix[i] /= nRadixBase / 10;
if (nDataRadix[i] > 0)
{
nIsOk = false;
}
}
if (nIsOk) //如果所有的基数都为0,认为排序完成,就是已经判断到最高位了。
{
break;
}
RadixCountSort(nDataRadix, 10, nPData, nLen);
}
free(nDataRadix);
return 1;
}
int main()
{
//测试基数排序。
int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888};
RadixSort(nData, 10);
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
#include <stdlib.h>
//计数排序,npRadix为对应的关键字序列,nMax是关键字的范围。npData是具体要
//排的数据,nLen是数据的范围,这里必须注意npIndex和npData对应的下标要一致
//也就是说npIndex[1] 所对应的值为npData[1]
int RadixCountSort(int* npIndex, int nMax, int* npData, int nLen)
{
//这里就不用说了,计数的排序。不过这里为了是排序稳定
//在标准的方法上做了小修改。
int* pnCount = (int*)malloc(sizeof(int)* nMax); //保存计数的个数
for (int i = 0; i < nMax; ++i)
{
pnCount[i] = 0;
}
for (int i = 0; i < nLen; ++i) //初始化计数个数
{
++pnCount[npIndex[i]];
}
for (int i = 1; i < 10; ++i) //确定不大于该位置的个数。
{
pnCount[i] += pnCount[i - 1];
}
int * pnSort = (int*)malloc(sizeof(int) * nLen); //存放零时的排序结果。
//注意:这里i是从nLen-1到0的顺序排序的,是为了使排序稳定。
for (int i = nLen - 1; i >= 0; --i)
{
--pnCount[npIndex[i]];
pnSort[pnCount[npIndex[i]]] = npData[i];
}
for (int i = 0; i < nLen; ++i) //把排序结构输入到返回的数据中。
{
npData[i] = pnSort[i];
}
free(pnSort); //记得释放资源。
free(pnCount);
return 1;
}
//基数排序
int RadixSort(int* nPData, int nLen)
{
//申请存放基数的空间
int* nDataRadix = (int*)malloc(sizeof(int) * nLen);
int nRadixBase = 1; //初始化倍数基数为1
bool nIsOk = false; //设置完成排序为false
//循环,知道排序完成
while (!nIsOk)
{
nIsOk = true;
nRadixBase *= 10;
for (int i = 0; i < nLen; ++i)
{
nDataRadix[i] = nPData[i] % nRadixBase;
nDataRadix[i] /= nRadixBase / 10;
if (nDataRadix[i] > 0)
{
nIsOk = false;
}
}
if (nIsOk) //如果所有的基数都为0,认为排序完成,就是已经判断到最高位了。
{
break;
}
RadixCountSort(nDataRadix, 10, nPData, nLen);
}
free(nDataRadix);
return 1;
}
int main()
{
//测试基数排序。
int nData[10] = {123,5264,9513,854,9639,1985,159,3654,8521,8888};
RadixSort(nData, 10);
for (int i = 0; i < 10; ++i)
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}
相关推荐
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在C++中实现基数排序,主要涉及到数组、计数排序以及位操作等技术。以下是关于基数排序及其C++实现的详细解释...
数据结构中的基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序并不是只能用于整数...
### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。递归算法则是一种解决问题的方法,它解决问题的每一个子问题都是原问题的缩小版,直到子问题简单到可以直接...
### 对10进制数进行基数排序的数据结构与算法实现 #### 1. 基数排序概述 基数排序是一种非比较型整数排序算法,它通过整数的各位数字来分配进桶的方式来进行排序。该算法对于固定大小的整数特别有效。基数排序的...
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如将数字转换为字符串形式),所以基数排序也可以很自然地扩展到...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法是通过分配、收集和再分配的步骤来实现的,它不依赖于元素之间的比较,而是依赖于数字的位数。这种...
### C++实现基数排序 #### 一、基数排序概述 基数排序是一种非比较型的整数排序算法。它通过对整数的每一位进行排序来达到整体序列的有序化。该算法的特点在于它不是通过元素间的相互比较来进行排序,而是通过按...
### Java实现基数排序算法 #### 实现原理 基数排序是一种非常高效的非比较型整数排序算法,它通过按数字的各个位数进行排序来实现序列的整体有序化。该算法的关键在于能够有效地处理多位数,避免了传统的两两比较...
基数排序是一种非比较型整数排序算法,它的核心在于将数字按位进行处理,从低位到高位逐位进行排序。这种排序方式适用于处理包含整数或者可以转换为整数形式的数据,如字符串。基数排序的关键在于“计数排序”...
### 链表基数排序的存储空间效率优化 #### 一、优化桶结构,降低空间消耗 在链表基数排序中,桶结构的选择对于优化存储空间有着至关重要的作用。优化桶结构可以从以下几个方面入手: 1. **基于哈希表的优化桶结构...
### 时间整数格式基数排序及转换为字符串形式 在计算机科学中,基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。基数排序通常用于那些不是通过比较元素大小来...
算法与数据结构,Java基数排序,归并排序,利用栈将四则表达式中缀转换为后缀并计算_Arithmetic
本资源是关于数据结构中排序算法的PPT课件,全文共118页,详细介绍了排序的概念、内部排序和外部排序、内部排序方法的分类、插入排序、快速排序、堆排序、归并排序、基数排序等内容。 1. 排序的概念:排序是计算机...
LSD法从最低位开始,按照每位的数值大小将元素分配到不同的桶中,然后收集回原位置,依次处理高位,直到所有位处理完,数组就按基数排序好了。基数排序的时间复杂度为O(kn),其中k是数字的最大位数,n是元素数量,...
计数排序与基数排序是两种非比较型排序算法。计数排序适用于一定范围内的整数排序,在特定条件下,它比基于比较的排序算法如快速排序、归并排序等拥有更好的时间复杂度。基数排序则是一种借助“基数”概念来按位数...
首先,对于排序部分,选择了基数排序这一非比较型整数排序算法。基数排序的基本思想是根据每位数字分别排序,从低位到高位,逐次进行。在本案例中,由于车牌号包括汉字、字母和数字,所以需要将汉字转换为对应的拼音...
程序设计上,主要包括以下几个函数:`main()`作为主函数,`Setlist()`用于添加车辆,`Distribute()`和`Collect()`分别用于基数排序的分配和收集阶段,`find()`执行二分查找,`menu()`提供用户交互界面,`print()`...
基数排序是一种基于分布的排序算法,它的思想是将待排序的数组根据关键字的每一位进行排序,首先根据低位的关键字进行排序,然后根据高位的关键字进行排序。基数排序的时间复杂度最好的情况下为 O(nk),最坏的情况下...