PHP数据结构（二十六） ——基数排序实现36进制数排序

<?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());