数据挖掘18大算法实现以及其他相关经典DM算法：决策分类，聚类，链接挖掘，关联挖掘，模式挖掘、图算法，搜索算法等
【机器学习入门与实践】入门必看系列，含数据挖掘项目实战：模型融合、特征优化、特征降维、探索性分析等，实战带你掌握机器学习数据挖掘
专栏详细介绍：【机器学习入门与实践】合集入门必看系列，含数据挖掘项目实战：数据融合、特征优化、特征降维、探索性分析等，实战带你掌握机器学习数据挖掘。
本专栏主要方便入门同学快速掌握相关知识。声明：部分项目为网络经典项目方便大家快速学习，后续会不断增添实战环节（比赛、论文、现实应用等）
专栏订阅：数据挖掘-机器学习专栏
主要讲解了数据探索性分析：查看变量间相关性以及找出关键变量；数据特征工程对数据精进：异常值处理、归一化处理以及特征降维；在进行归回模型训练涉及主流ML模型：决策树、随机森林，lightgbm等。同时重丶讲解模型验证、特征优化、模型融合等。
数据挖掘18大算法实现以及其他相关经典DM算法：决策分类，聚类，链接挖掘，关联挖掘，模式挖掘、图算法，搜索算法等码源链接见文末or文章顶部1.十八大DM算法目录包名目录名算法名AssociationAnalysisDataMining_AprioriApriori-关联规则挖掘算法AssociationAnalysisDataMining_FPTreeFPTree-频繁模式树算法BaggingAndBoostingDataMining_AdaBoostAdaBoost-装袋提升算法ClassificationDataMining_CARTCART-分类回归树算法ClassificationDataMining_ID3ID3-决策树分类算法ClassificationDataMining_KNNKNN-k最近邻算法工具类ClassificationDataMining_NaiveBayesNaiveBayes-朴素贝叶斯算法ClusteringDataMining_BIRCHBIRCH-层次聚类算法ClusteringDataMining_KMeansKMeans-K均值算法GraphMiningDataMining_GSpanGSpan-频繁子图挖掘算法IntegratedMiningDataMining_CBACBA-基于关联规则的分类算法LinkMiningDataMining_HITSHITS-链接分析算法LinkMiningDataMining_PageRankPageRank-网页重要性/排名算法RoughSetsDataMining_RoughSetsRoughSets-粗糙集属性约简算法SequentialPatternsDataMining_GSPGSP-序列模式分析算法SequentialPatternsDataMining_PrefixSpanPrefixSpan-序列模式分析算法StatisticalLearningDataMining_EMEM-期望最大化算法StatisticalLearningDataMining_SVMSVM-支持向量机算法2.其他经典DM算法包名目录名算法名OthersDataMining_ACOACO-蚁群算法OthersDataMining_BayesNetworkBayesNetwork-贝叶斯网络算法OthersDataMining_CABDDCCCABDDCC-基于连通图的分裂聚类算法OthersDataMining_ChameleonChameleon-两阶段合并聚类算法OthersDataMining_DBSCANDBSCAN-基于密度的聚类算法OthersDataMining_GAGA-遗传算法OthersDataMining_GA_MazeGA_Maze-遗传算法在走迷宫游戏中的应用算法OthersDataMining_KDTreeKDTree-k维空间关键数据检索算法工具类OthersDataMining_MSAprioriMSApriori-基于多支持度的Apriori算法OthersDataMining_RandomForestRandomForest-随机森林算法OthersDataMining_TANTAN-树型朴素贝叶斯算法OthersDataMining_ViterbiViterbi-维特比算法3.十八大经典DM算法详解18大数据挖掘的经典算法以及代码实现，涉及到了决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面,后面都是相应算法的博文链接，希望能够帮助大家学。目前追加了其他的一些经典的DM算法，在others的包中涉及聚类，分类，图算法，搜索算等等，没有具体分类。
C4.5C4.5算法与ID3算法一样，都是数学分类算法，C4.5算法是ID3算法的一个改进。ID3算法采用信息增益进行决策判断，而C4.5采用的是增益率。详细介绍链接
CARTCART算法的全称是分类回归树算法，他是一个二元分类，采用的是类似于熵的基尼指数作为分类决策，形成决策树后之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法，详细介绍链接
KNNK最近邻算法。给定一些已经训练好的数据，输入一个新的测试数据点，计算包含于此测试数据点的最近的点的分类情况，哪个分类的类型占多数，则此测试点的分类与此相同，所以在这里,有的时候可以复制不同的分类点不同的权重。近的点的权重大点，远的点自然就小点。详细介绍链接
NaiveBayes朴素贝叶斯算法。朴素贝叶斯算法是贝叶斯算法里面一种比较简单的分类算法，用到了一个比较重要的贝叶斯定理，用一句简单的话概括就是条件概率的相互转换推导。详细介绍链接
SVM支持向量机算法。支持向量机算法是一种对线性和非线性数据进行分类的方法，非线性数据进行分类的时候可以通过核函数转为线性的情况再处理。其中的一个关键的步骤是搜索最大边缘超平面。详细介绍链接
EM期望最大化算法。期望最大化算法，可以拆分为2个算法，1个E-Step期望化步骤,和1个M-Step最大化步骤。他是一种算法框架，在每次计算结果之后，逼近统计模型参数的最大似然或最大后验估计。详细介绍链接
AprioriApriori算法是关联规则挖掘算法，通过连接和剪枝运算挖掘出频繁项集，然后根据频繁项集得到关联规则，关联规则的导出需要满足最小置信度的要求。详细介绍链接
FP-Tree频繁模式树算法。这个算法也有被称为FP-growth算法，这个算法克服了Apriori算法的产生过多侯选集的缺点，通过递归的产生频度模式树，然后对树进行挖掘，后面的过程与Apriori算法一致。详细介绍链接
PageRank网页重要性/排名算法。PageRank算法最早产生于Google,核心思想是通过网页的入链数作为一个网页好快的判定标准，如果1个网页内部包含了多个指向外部的链接，则PR值将会被均分，PageRank算法也会遭到LinkSpan攻击。详细介绍链接
HITSHITS算法是另外一个链接算法，部分原理与PageRank算法是比较相似的，HITS算法引入了权威值和中心值的概念，HITS算法是受用户查询条件影响的，他一般用于小规模的数据链接分析，也更容易遭受到攻击。详细介绍链接
K-MeansK-Means算法是聚类算法，k在在这里指的是分类的类型数，所以在开始设定的时候非常关键，算法的原理是首先假定k个分类点，然后根据欧式距离计算分类，然后去同分类的均值作为新的聚簇中心，循环操作直到收敛。详细介绍链接
BIRCHBIRCH算法利用构建CF聚类特征树作为算法的核心，通过树的形式，BIRCH算法扫描数据库，在内存中建立一棵初始的CF-树，可以看做数据的多层压缩。详细介绍链接
AdaBoostAdaBoost算法是一种提升算法，通过对数据的多次训练得到多个互补的分类器，然后组合多个分类器，构成一个更加准确的分类器。详细介绍链接
GSPGSP算法是序列模式挖掘算法。GSP算法也是Apriori类算法，在算法的过程中也会进行连接和剪枝操作，不过在剪枝判断的时候还加上了一些时间上的约束等条件。详细介绍链接
PreFixSpanPreFixSpan算法是另一个序列模式挖掘算法，在算法的过程中不会产生候选集，给定初始前缀模式，不断的通过后缀模式中的元素转到前缀模式中，而不断的递归挖掘下去。详细介绍链接
CBA基于关联规则分类算法。CBA算法是一种集成挖掘算法，因为他是建立在关联规则挖掘算法之上的，在已有的关联规则理论前提下，做分类判断，只是在算法的开始时对数据做处理，变成类似于事务的形式。详细介绍链接
RoughSets粗糙集算法。粗糙集理论是一个比较新颖的数据挖掘思想。这里使用的是用粗糙集进行属性约简的算法，通过上下近似集的判断删除无效的属性，进行规制的输出。详细介绍链接
GSpangSpan算法属于图挖掘算法领域。，主要用于频繁子图的挖掘，相较于其他的图算法，子图挖掘算法是他们的一个前提或基础算法。gSpan算法用到了DFS编码，和Edge五元组，最右路径子图扩展等概念，算法比较的抽象和复杂。详细介绍链接
4.Others目录下的算法详解：GA遗传算法。遗传算法运用了生物进化理论的知识来寻找问题最优解的算法，算法的遗传进化过程分选择，交叉和变异操作，其中选择操是非常关键的步骤，把更适应的基于组遗传给下一代。详细介绍链接
DbScan基于空间密度聚类算法。dbScan作为一种特殊聚类算法，弥补了其他算法的一些不足，基于空间密，实现聚类效果，可以发现任意形状的聚簇。详细介绍链接
GA_Maze遗传算法在走迷宫游戏中的应用。将走迷宫中的搜索出口路径的问题转化为遗传算法中的问题通过构造针对此特定问题的适值函数，基因移动方向的定位，巧的进行问题的求解。详细介绍链接
CABDDCC基于连通图的分裂聚类算法。也是属于层次聚类算法主要分为2个阶段，第一阶段构造连通图。第二个阶段是分裂连通图，最终形成聚类结果。详细介绍链接
Chameleon两阶段聚类算法。与CABDDCC算法相反，最后是通过对小簇集合的合并，形成最终的结果，在第一阶段主要是通过K近邻的思想形成小规模的连通图，第二阶段通过RI(相对互连性)和RC(相对近似性)来选一个最佳的簇进行合并。详细介绍链接
RandomForest随机森林算法。算法思想是决策树+boosting.决策树采用的是CART分类回归数,通过组合各个决策树的弱分类器,构成一个最终的强分类器,在构造决策树的时候采取随机数量的样本数和随机的部分属性进行子决策树的构建,避免了过分拟合的现象发生。详细介绍链接
KDTreeK-DimensionTree。多维空间划分树，数据在多维空间进行划分与查找。主要用于关键信息的搜索，类似于在空间中的二分搜索，大大提高了搜索效率，在寻找目标元素时，使用了DFS深度优先的方式和回溯进行最近点的寻找。详细介绍链接
MS-Apriori基于多支持度的Apriori算法。是Apriori算法的升级算法，弥补了原先Apriori算法的不足，还增加了支持度差别限制以及支持度计数统计方面的优化，无须再次重新扫描整个数据集，产生关联规则的时候可以根据子集的关系避免一些置信度的计算。详细介绍链接
ACO蚁群算法。蚁群算法又称为蚂蚁算法。同GA遗传算法类似，也是运用了大自然规律的算法，用于在图中寻找最优路径的概率型算法。灵感来源于蚂蚁在寻找食物时会散播信息素的发现路径行为。详细介绍链接
BayesNetwork贝叶斯网络算法。弥补了朴素贝叶斯算法中必须要事件独立性的缺点，利用了贝叶斯网络的DAG有向无环图，允许各个事件保留一定的依赖关系，网络结构中的每个节点代表一种属性，边代表相应的条件概率值，通过计算从而能得到精准的分类效果。详细介绍链接
TAN树型朴素贝叶斯算法。此算法又被称为加强版朴素贝叶斯算法。在满足原有朴素贝叶斯条件的基础上，他允许部条件属性直接的关联性。形成树型的结构。详细介绍链接
Viterbi维特比算法。给定一个隐马尔科夫模型以及一个观察序列，求出潜在的状态序列信息，每个潜在状态信息又会受到前一个状态信息的影响。
5.算法使用方法在每个算法中给出了3大类型，主算法程序，调用程序，输入数据，调用方法如下：
将需要数据的测试数据转化成与给定的输入格式相同然后以Client类的测试程序调用方式进行使用。也可以自行修改算法程序，来适用于自己的使用场景码源链接见文末or文章顶部如果无法下载，过几天在来试试，应该在审核中
下载链接：
https://download.csdn.net/download/sinat_39620217/87990416
十大排序算法（Java实现）
文章目录零、总览/前言一、冒泡排序1.算法描述2.代码&复杂度二、选择排序1.算法描述2.代码&复杂度三、插入排序1.算法描述2.代码&复杂度分析四、希尔排序1.算法步骤2.代码&复杂度分析五、归并排序1.算法描述2.代码&复杂度分析六、快速排序1.算法描述2.代码&复杂度分析七、堆排序八、计数排序——非比较排序1.算法描述2.代码&复杂度分析九、基数排序——非比较排序十、桶排序——非比较排序零、总览/前言复杂度和稳定性表格一览
排序算法平均时间最好时间最坏时间空间稳定性冒泡O(n2)O(n^2)O(n2)O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(1)O(1)O(1)稳定选择O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)不稳定插入O(n2)O(n^2)O(n2)O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(1)O(1)O(1)稳定希尔O(1)O(1)O(1)不稳定归并O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n)O(n)O(n)稳定快排O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n2)O(n^2)O(n2)O(logn)O(logn)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(1)O(1)O(1)不稳定计数排序O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)O(n+k)稳定基数排序稳定桶排序O(n)O(n)O(n)O(n)O(n)O(n)O(1)O(1)O(1)稳定解释一下稳定性：对于存在相等元素的序列，排序后，原相等元素在排序结果中的相对位置相比原输入序列不变。例如nums={3,1,212_121,222_222}，数字2出现了两次，下标表示他们出现的次序，若排序方法将nums排成了{1,222_222,212_121,3}，虽然排序结果正确，但改变了两个2的相对位置。只有排序为{1,212_121,222_222,3}我们才说该排序是稳定的。
如果排序对象只是数值，那么是否稳定没有区别。但若是对引用类型进行排序，排序依据是该类型中的某个可比较的数值字段，那么我们可能会希望该字段相同，但其他字段不同的元素相对位置相比原输入保持不变，这时候就需要稳定排序。
不稳定排序算法堆排序、快速排序、希尔排序、直接选择排序
稳定排序算法基数排序、冒泡排序、插入排序、归并排序
一、冒泡排序1.算法描述对于要排序的数组，从第一位开始从前往后比较相邻两个数字，若前者大，则交换两数字位置，然后比较位向右移动一位。第1轮从前到后的比较将使得最大的数字冒泡到最后
接着第二轮，同样的操作，只不过只需要比到倒数第二个（倒数第一已经最大了）
重复以上操作……
2.代码&复杂度//冒泡排序，从小到大排序，比较相邻元素，更大的往数组右边移动staticvoidbubbleSort3(int[]arr){for(inti=arr.length-1;i>0;i--){for(intj=0;jinttmp=arr[j];arr[j]=arr[j+1];arr[j+1]=tmp;}}}}时间复杂度：O(n^2)空间复杂度：O(1）
二、选择排序1.算法描述步骤：（1）长度为n的数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换
（2）第二次遍历n-2个数，找到最小的数值与第二个元素交换
（3）第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成
2.代码&复杂度publicvoidselectSort3(int[]arr){for(inti=0;iif(minTmp>arr[j]){//每次找到更小的时候记录数字和下标值minTmp=arr[j];index=j;}}//本轮循环结束，将最小值交换到数组前方inttemp=arr[i];arr[i]=minTmp;arr[index]=temp;}时间复杂度：O(n^2)空间复杂度：O(1）
三、插入排序1.算法描述插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列
算法步骤：（1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
（2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
2.代码&复杂度分析/*插入排序：从小到大排序，类似于打扑克牌*/staticvoidinsertSort(int[]arr){for(inti=1;iarr[j+1]=arr[j];j--;}arr[j+1]=now;}}时间复杂度：O(n^2)——i遍历一次，j遍历了一次，所以n^2空间复杂度：O(1)——原地修改，没有用额外空间
四、希尔排序1.算法步骤先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
2.代码&复杂度分析//希尔排序：从小到大staticvoidshellSort(int[]arr){for(intinterval=arr.length/2;interval>0;interval=interval/2){for(inti=interval;iarr[j+interval]=arr[j];j-=interval;}arr[j+interval]=temp;}}}时间复杂度：空间复杂度：
五、归并排序1.算法描述分而治之，先分治，再合并
2.代码&复杂度分析publicstaticvoidmain(String[]args){int[]arr={5,3,8,6,2,7};mergeSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}//自顶向下，递归实现publicstaticvoidmergeSort(int[]arr,intleft,intright){if(leftint[]temp=newint[arr.length];inti=left;intj=mid+1;intk=left;while(itemp[k++]=arr[i++];}else{temp[k++]=arr[j++];}}while(itemp[k++]=arr[j++];}for(intm=left;mif(left>right)return;intpivot=arr[left];inti=left;intj=right;while(i!=j){while(i=pivot)j--;while(iintminNum=0,maxNum=0;//先求出数组中的最大值和最小值for(intnum:arr){minNum=Math.min(minNum,num);maxNum=Math.max(maxNum,num);}//开辟一个新数组：计数数组int[]count=newint[maxNum-minNum+1];//遍历原数组，对应计数数组索引值++for(intnum:arr){count[num-minNum]++;}//开始将计数数组输出intindex=0;for(inti=0;iarr[index++]=i;count[i]--;}}returnarr;}时间复杂度：O(n+k)，n为元素个数，k计数数组大小
空间复杂度：O(k)
上面的还是属于不稳定版本的，稳定版本可以参见：https://leetcode.cn/circle/discuss/eBo9UB/
九、基数排序——非比较排序十、桶排序——非比较排序参考链接：https://leetcode.cn/circle/discuss/eBo9UB/
c++十大经典排序算法（续接上文）
这是上次的介绍，不知道的点开这个：https://blog.csdn.net/back_room/article/details/131338517?spm=1001.2014.3001.5502
上期我们讲了这些算法：
选择排序、插入排序、冒泡排序、希尔排序、快速排序。
现在我们来讲剩下的其中两个：归并排序，堆排序
（后续会讲基数排序，计数排序，桶排序）
归并排序（MergeSort）归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（DivideandConquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
1.基本思想归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
分解（Divide）：将n个元素分成个含n/2个元素的子序列。解决（Conquer）：用合并排序法对两个子序列递归的排序。合并（Combine）：合并两个已排序的子序列已得到排序结果。2.实现逻辑2.1迭代法
①申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列②设定两个指针，最初位置分别为两个已经排序序列的起始位置③比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置④重复步骤③直到某一指针到达序列尾⑤将另一序列剩下的所有元素直接复制到合并序列尾2.2递归法
①将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素②将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素③充复步骤②，直到所有元素排序完毕归并排序演示
具体的我们以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示
上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
4.复杂度分析平均时间复杂度：O(nlogn)最佳时间复杂度：O(n)最差时间复杂度：O(nlogn)空间复杂度：O(n)排序方式：In-place稳定性：稳定不管元素在什么情况下都要做这些步骤，所以花销的时间是不变的，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为：O(nlogn)
归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n+logn；所以空间复杂度为:O(n)。
归并排序算法中，归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法。
堆排序
（英语：Heapsort）
是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆节点的访问编辑
通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：
父节点i的左子节点在位置(2i+1）;
父节点i的右子节点在位置(2i+2）;
子节点i的父节点在位置floor((i-1)/2);
2.堆的操作编辑
在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：
最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
原地堆排序基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是：
创建一个堆H（0..n-1）;
平均复杂度堆排序的平均时间复杂度为0(nlogn);
空间复杂度为O(1)
c++十大经典排序（继接上文）
不知道点开
https://blog.csdn.net/back_room/article/details/131338517?spm=1001.2014.3001.5502
c++十大经典排序算法（续接上文）_Whitney-kola的博客-CSDN博客
基数排序（radixsort）属于“分配式排序”（distributionsort），又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
中文名 基数排序
外文名 Radixsort
别 名 “桶子法”
类 别 分配式排序
方 法 最高位优先法和最低位优先
发明者 赫尔曼·何乐礼
领 域 计算机算法
基本解法第一步以LSD为例，假设原来有一串数值如下所示：
73,22,93,43,55,14,28,65,39,81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
181
222
3739343
414
55565
6
7
828
939
第二步接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81,22,73,93,43,14,55,65,28,39
接着再进行一次分配，这次是根据十位数来分配：
0
114
22228
339
443
555
665
773
881
993
第三步接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14,22,28,39,43,55,65,73,81,93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
效率分析时间效率 [1] ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
实现方法最高位优先(MostSignificantDigitfirst)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
最低位优先(LeastSignificantDigitfirst)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
实现原理基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(TabulationMachine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
基数排序的方式可以采用LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
AAuto第一步io.open();//打开控制台
/*
*-------------------------------------------------------
*基数排序
**------------------------------------------------------
*/
/*
第二步基数排序从低位到高位进行，使得最后一次计数排序完成后，数组有序。
其原理在于对于待排序的数据，整体权重未知的情况下，
先按权重小的因子排序，然后按权重大的因子排序。
例如比较时间，先按日排序，再按月排序，最后按年排序，仅需排序三次。
但是如果先排序高位就没这么简单了。
基数排序源于老式穿孔机，排序器每次只能看到一个列，
很多教科书上的基数排序都是对数值排序，数值的大小是已知的，与老式穿孔机不同。
将数值按位拆分再排序，是无聊并自找麻烦的事。
算法的目的是找到最佳解决问题的方案，而不是把简单的事搞的更复杂。
基数排序更适合用于对时间、字符串等这些整体权值未知的数据进行排序。
这时候基数排序的思想才能体现出来，例如字符串，如果从高位（第一位）往后排就很麻烦。
而反过来，先对影响力较小，排序排重因子较小的低位（最后一位）进行排序就非常简单了。
这时候基数排序的思想就能体现出来。
又或者所有的数值都是以字符串形式存储，就象穿孔机一样，每次只能对一列进行排序。
这时候基数排序也适用，例如：对{"193";"229";"233";"215"}进行排序
下面我们使用基数排序对字符串进行排序。
对每个位循环调用计数排序。
*/
第三步//计数排序算法
radix_sort=function(array,maxlen){
//AAuto在字符串索引越界时，会返回0，这使基数排序的实现更加简单。
//我们首先找出最大的排序长度，然后对于不足此长度的字符串，尾部都假定以0补齐。
//对于超出此长度的位在比较时忽略
if(!maxlen){
maxlen=0;
for(i=1;#array;1){
maxlen=math.max(maxlen,#array[i])
}
}
//else{
//最大排序长度也可以从参数中传过来，这样就不用遍历所有字符串了
//}
第四步//从字符串的最后一位开始，到第一位
for(pos=maxlen;1;-1){
//按当前位的字节码计数排序
vararray_sorted={};
varcount={};
for(i=0;256){
count[i]=0;
}
varbytecode;
for(i=1;#array;1){
//如果pos大于字符串长度，AAuto会返回0，这使基数排序的实现更容易
bytecode=array[i][pos];
count[bytecode]++;//count[n]包含等于n的个数
}
第五步//统计位置
for(i=1;256;1){
count[i]+=count[i-1];//count[i]包含小于等于i的个数
}
varn;
for(i=#array;1;-1){
n=array[i][pos]
array_sorted[count[n]]=array[i];
count[n]--;//防止相同的元素n再次出现，将计数减一
}
array=array_sorted;
}
returnarray
}
io.print("----------------")
io.print("基数排序(线性时间排序)")
io.print("----------------")
array={"AAutoisquickerandbetter,justtryit!";"AAutoQuicker";"193";"229";"233";"215";"HelloWord";"abc";"abcd";"xd";"adcd";"eddd";"ah";"ai";"aj";"ajkk"};
第六步//排序
array=radix_sort(array)
第七步//输出结果
for(i=1;#array;1){
io.print(array[i])
}
execute("pause")//按任意键继续
io.close();//关闭控制台
下次会一次性讲完剩下两个