PHP数据结构(二十六)——基数排序实现36进制数排序
(原创内容,转载请注明来源,谢谢)
一、概述
插入排序、选择排序、快速排序等,都是通过关键字之间的比较和移动进行的。基数排序完全不同,其是借助多个关键字排序的思想对单逻辑关键字进行排序的方法。
所谓多关键字,可以理解为带权值的关键字。例如:
现有序列{a0,a1,a2,a3,b0,b1,b2,b3},假设a<b,数字按数字正常的大小。现要求对这个序列进行排序,但是要求数字的优先级更高,即a0<b0<a1<b1。则这种排序可以认为是多关键字的排序。
1、序列对关键字有序的定义
假设序列{r1,r2…rn},每个ri均有d个关键字(k1,k2…kd)。当ri排在rj前面时,ri对应的任意ki都比rj对应的任意kj小(或大)。则成为序列按关键字有序。
2、排序的两种方式
1)最高位优先法(MSD法)
先按最高位排好,再排次高位,直至最低位。按上面例子,先按照数字排好,再在排好的序列中去排字母的顺序。
2)最低位优先法(LSD法)
先按最低位排好,再排次低位,直至最高为。按上面例子,先按字母排好,根据字母个数分成x组,再各组之间互相比较高级别的关键字。
3)比较
MSD法必将序列分割成若干个子序列,然后对子序列进行排序。
LSD法不用将内容进行分割,每次都是整个序列参加排序,但是对除了最底层以外的排序外,其他排序必须用稳定的排序。另外,也可以通过“分配”和“收集”的方式进行排序。
二、链式基数排序
链式基数排序,采用队列+链表的方式,将整个序列用链表串起来,头指针指向序列的第一个元素。接着采用LSD法,先遍历最后一个元素,当元素有n种时,同时使用n个指针(例如对数字遍历,则同时用10个指针,指向0-9),指向n1,n2…n为结尾的。接着再遍历第二次,直至遍历n次,串起来的即为排好序的内容。
1、算法
1)根据输入结果的位数,判断输入的元素有几位数,对于不足最长位数的,开头的地方进行补全,值设置为最小结果。(例如三位数字中,出现两位数,则第一位补0)
2)分析输入的数字,区分一共有几种内容。用于后面设定指针,不需要设置最大指针,可以根据实际动态设置。(例如三位字母数字混合字符串比较,只输入了a01,b23,a56,则只需要分配指针给a、b、0、1、2、3、5、6,而不需要分配26+10=36个指针)
3)设置一个头指针,指向序列的第一个元素,并且将第一个元素指向第二个元素,直至将元素串起来。
4)循环进行LSD,循环次数为元素的最大长度。循环做下列5、6两项内容,直到完成循环次数。
5)首先判断最低位,从头指针一直往后读取数据,将不同的最低位以队列的方式进入表示不同权值的指针。
6)将指针按权值从低到高,按照队列先进先出的方式,将所有数据再串成序列。
7)完成后,将序列返回,即为排好序的序列。
2、假设3位数进行排序,则共需要3轮,如下图所示(图片是数据结构书的内容)
3、程序概述
1)场景
现对序列array('a01','1g5', 'a8j', '13b', 'dx5', 'az', '10', '1cz', '0')进行基数排序,排序要求:从小到大,数字比字母小,0,1,2…9,a,b,c…z为从小到大的顺序。另外,比较规则类似于十进制的比较,如9<10,即虽然0<z,但是10>z。
因此,该程序实现36进制数的比较。另外,程序的大小比较是通过实例化类时传的参数进行的,因此,可以根据需要动态的改变比较规则。
2)实现过程
分几步进行实现。
a.定义一个节点类Node,用做链表里面的节点。
b.定义构造函数和__set()方法,用于设置比较方式。
c.定义函数用于通过用户输入的序列,获取序列元素的最长值。
d.定义函数用于通过用户输入的序列,生成包含序列元素下标的数组,每个下标有一个空数组,用做指针,在比较期间存放数据。
e.定义函数,根据序列以及c步骤获取的最大字符串长度,生成链表。
f.进入循环,遍历链表,首先看每个元素的末位,并根据末位的位置放置于d步骤生成的数组的相应地方。接着将此数组重组成链表。循环此步骤,从末位开始一直做到首位。则此时的链表已经是按照自定义规则比较的元素从小到大排序的链表了。
g.将链表转回成数组,由于一开始将不足的长度补全,故再次步骤需要将开头位是最小值的去掉,但是如果全部都是最小值,则留下一个字符。(可以理解成十进制的0078中的前两个0去掉,留下78;但是如果是0000则只去掉3个0,留下0)。此数组即为最终的按自定义规则从小到大比较排序的数组。
4、程序执行结果
5、程序源码
<?php
class Node{ public$data; public$next;}
//基数排序实现类
class SortArrayMulty{
private$arr;//用于比较的数组
private$type;//排序方式
publicfunction __construct(array $arr = array(), array $type = array()){
$this->arr= $arr;
//默认支持0-9以及小写a-z,且数字优先级比字母高
if(empty($type)){
$this->type= array( '0','1', '2', '3', '4', '5', '6', '7', '8', '9', 'a','b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k','l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u','v', 'w', 'x', 'y', 'z' );
}else{
$this->type= $type;
}
}
//设置排序方式
publicfunction __set($prop, $res){
if(!property_exists($this,$prop)){
returnfalse;
}
if(!is_array($res)){
returnfalse;
}
$this->$prop= $res;
}
//主要用于查看排序方式
publicfunction __get($prop){
if(!property_exists($this,$prop)){
returnfalse;
}
return$this->$prop;
}
//基数排序主方法
publicfunction baseNumSort(array $arr = array()){
if(empty($arr)){
$arr= $this->arr;
}
if(1>= $arr){
return$arr;
}
//判断位数
$strLength= $this->_getLongestStrLength($arr);
//判断种类数,并根据type进行排序,返回排好序的数组array('type1'=>array(),'type2'=>array()...)
$arrTypes= $this->_getStrTypes($arr);
//初始化链表,如果长度不足,从前面补最小字符 chainHead{data=null;next={data=val1;next={data=val2,next=....}}}
$chainHead= $this->_initChain($arr, $strLength);
//循环次数
$loopNum= 0;
while($loopNum< $strLength){
$findIndex= $strLength - 1 - $loopNum;//第0次查找第strLength-1位,第1次查找第strLength-2位,第loopNum次查找第strLength-1-loopNum位
$curNode= $chainHead->next;
while(null!= $curNode){
$curData= $curNode->data; //获取当前值
//获取当前正在比较的字符的值,并根据下标将当前字符值放进相应的数组
$curWorld= strval($curData[$findIndex]);
array_push($arrTypes[$curWorld],$curData);
$curNode= $curNode->next;
}
//根据生成的数组指针,重新合成链表序列,需要安装types来进行排序
$chainHead= $this->_rebuildChain($arrTypes);
//将数组指针的内容情况,仅保留类型
$arrTypes= $this->_cleanSelf($arrTypes);
$loopNum++;
}
//将指针转回成一维数组
return$this->_convertChainToArray($chainHead);
}
//获取序列中字符串最长的字符数量
privatefunction _getLongestStrLength(array $arr){
$maxLength= 0;
//如果大于maxlength则赋值给maxlength
foreach($arras $str){
if(strlen($str)> $maxLength){
$maxLength= strlen($str);
}
}
return$maxLength;
}
//判断序列有哪几种字符,并根据type进行排序,返回排好序的数组
privatefunction _getStrTypes(array $arr){
$arrTypes= array();
//遍历序列
foreach($arras $str){
$curLength= strlen($str);
//遍历每个字符,没有则加上
for($i=0;$i<$curLength;$i++){
if(!in_array(strval($str[$i]),$arrTypes)){
$arrTypes[]= strval($str[$i]);
}
}
}
$type= $this->type;
//对$arrTypes按照type进行排序,返回有序内容
$arrRes= array();
foreach($typeas $item){
if(in_array($item,$arrTypes)){
$arrRes[$item]= array();
}
}
return$arrRes;
}
//将序列初始化成链表
privatefunction _initChain(array $arr, $strLength){
//定义链表头
$head= new Node();
$tmpNode= $head;
$type= $this->type;
$minWord= $type[0];
foreach($arras $node){
//定义下一个节点
$tmpNode->next= new Node();
$tmpNode= $tmpNode->next;
//如果字符长度不足,则前面不齐最小值
if(strlen($node)< $strLength){
$repeatStr= str_repeat($minWord, $strLength-strlen($node));
$node= $repeatStr . $node;
}
$tmpNode->data= $node;
}
return$head;
}
//将数组重组成链表
privatefunction _rebuildChain(array $arrTypes){
//定义表头
$head= new Node();
$tmpNode= $head;
//遍历arrtypes数组生成链表
foreach($arrTypesas $items){
//如果节点为空则遍历下一个
if(empty($items)){
continue;
}
//遍历数组中的元素,按顺序拼接回链表
foreach($itemsas $item){
$tmpNode->next= new Node();
$tmpNode= $tmpNode->next;
$tmpNode->data= $item;
}
}
return$head;
}
//清空数组内的元素,仅保留关键字
privatefunction _cleanSelf(array $arrTypes){
foreach($arrTypesas $type => $arr){
$arrTypes[$type]= array();
}
return $arrTypes;
}
//将指针转回成一维数组
privatefunction _convertChainToArray(Node $head){
$arrRes= array();
$curNode= $head->next;
//获取最小值
$type= $this->type;
$minWorld= $type[0];
while(null!= $curNode){
//转回一维数组需要进行处理,开头几位如果有最小值(0)则应该去掉
$minWorldLength= 0;
$data= $curNode->data;
$len= strlen($data);
//如果全部是0,则保留一个0,故只遍历到$len-2即可
while($minWorldLength<= $len - 2){
if($minWorld!= $data[$minWorldLength]){
break;
}
$minWorldLength++;
}
$data= substr($data, $minWorldLength);
array_push($arrRes,$data);
$curNode= $curNode->next;
}
return$arrRes;
}
}
$arrToSort = array('a01','1g5', 'a8j', '13b', 'dx5', 'az', '10', '1cz', '0');
$sortArrayMuti = newSortArrayMulty($arrToSort);
print_r($sortArrayMuti->baseNumSort());
——written by linhxx 2017.07.21
相关阅读: