多字段排序 -- PHP版
上期单机redis平稳重启的我的解决办法：
用不同的端口来搭建一个cluster，这样就可以不中断服务重启了，而且，管理多块小内存可能比管理一大块内存要好。
闲来有空，说一下自己写的一个多字段排序算法。
之前有一个需求是每日更新游戏排行榜，需要把近7天新增的游戏评价集合，计算平均分，按平均分倒序排列，平均分相等的按照游戏发行时间倒序来排。
数据库设计的时候是按照游戏id进行hash，对10取模获取游戏评价表名的。然而把数据集合起来之后，需要对数据进行重新排序，这里就不能用mysql的order by了。（其实也可以的，新建一个临时表来查询，但是估计没人想用这么傻的方法）
既然这样，就需要自己手写一个多字段排序的算法来解决这个问题了。（先说一下结果，我写完之后，发现php有现成的function可以用，array_multisort，看官们可以去查一下手册看用法，但是我自己写的这个还有另外一个用处，就是对不进行排序的字段可以一并保留输出。但从性能来说，肯定是php原生的function会高得多，所以要看情况来使用）
首先来明确一下思路，对一个 list 进行排序（这里我用 list，因为 set 没有重复值，list更符合大多数情况），排序有顺序和倒序。list 中 n 个元素前面 j 个值都相同，则比较下一级字段，如果所有字段的值都相等，则这 n 个元素可以视为相同，则只要它们的排序是相连的即可。另外，如果某两个元素全部字段都相等，它们可以互换位置，也可以不换位置。如果换位置，这个排序就称为不稳定的，反之就是稳定的。
ps：我写的这个算法是不稳定的。。。o(╥﹏╥)o
做法：建立一个新的空 list，从输入的 list 取出一个（头尾都可）这里称为tmp，按顺序去跟新的 list 中的元素比较（顺序搜索法），如果搜索到一个元素是，按照当前排序规则是可以排在当前元素的前面的，或者两元素相等，则让tmp占据新 list 的当前位置，当前元素及其后面的元素依次往后移动（插入排序）。到最后如果搜索不到符合条件的元素，则让tmp直接进入队尾。说的有点多，来看代码。talk is cheap，show me the code。
/**
* [multiSortArray 数组多字段排序(算法为顺序搜索和插入排序，是不稳定的排序，但可以维持其他不排序字段不变，时间复杂度大概是O(n²)，空间复杂度不会算)，不关心非排序字段可用PHP原生函数：array_multisort ()]
* @author [KAEL] <[<email address>]>
* @param [Array] $arr [原数组]
* @param [Array] $fields [排序字段]
* @param [Array] $sorts [排序规则,正序传SORT_ASC，倒序传SORT_DESC]
* @return [type] [description]
*/
public static function multiSortArray(Array $arr, Array $fields, Array $sorts) {
// 这里的$sorts的长度可以$fields少，不足的按照最后一个补齐，让调用者可以稍微偷点懒
// 以下代码都是进行参数验证的代码，可以忽略不看，是为了程序的鲁棒性-----------------------
if (empty($arr) || empty($fields) || empty($sorts)) {
return false;
}
// 二维数组
$arr = array_values($arr);
if (!is_array($arr[0])) {
return false;
}
$fields = array_values($fields);
$sorts = array_values($sorts);
$tmp = array_unique($sorts);
$sortType = array(SORT_ASC, SORT_DESC);
if ((!in_array($tmp[0], $sortType)) || (isset($tmp[1]) && !in_array($tmp[1], $sortType))) {
return false;
}
$tmp = array_slice($sorts, -1, 1);
$tmp = $tmp[0];// 最后一个排序
$sorts = array_pad($sorts, count($fields), $tmp);// 填充排序数组
foreach ($fields as $key => $value) {
if (!is_string($value) || !isset($arr[0][$value])) {
return false;
}
}
$fcount = count($fields);
$list = array();
$list[] = array_shift($arr);
// 以上代码都是进行参数验证的代码，可以忽略不看，是为了程序的鲁棒性-----------------------
while ($tmp = array_shift($arr)) {
$count = count($list);
$flag = false;// 一个标记是否有进行插入排序的flag
foreach ($list as $key => $value) {
if (self::recurseCompare($tmp, $value, $fields, $sorts, 0)) {
// 匹配成功就进行插入排序
for ($i = $count; $i > $key; --$i) {
$list[$i] = $list[$i-1];
}
$list[$key] = $tmp;
$flag = true;
break;
}
}
if (!$flag) {
// 插入队尾
array_push($list, $tmp);
}
}
return $list;
}
以下是字段比较的递归算法：
/**
* [recurseCompare 多字段排序递归比较]
* @param [Array] $var1 [变量1]
* @param [Array] $var2 [变量2]
* @param [Array] $fields [字段数组]
* @param [Array] $sorts [排序数组]
* @param [integer] $index [比较字段索引]
* @return [type] [description]
*/
private static function recurseCompare(Array $var1, Array $var2, Array $fields, Array $sorts, $index = 0) {
$index = intval($index);
$key = $fields[$index];
$count = count($fields);
if (!is_numeric($var1[$key]) && is_string($var1[$key])) {
// 字符串排序，英文的，中文别想了，大兄dei
$res = StrUtil::dictCompare($var1[$key], $var2[$key]);
// -1表示 val1 比 val2 小，0表示相等，1表示 val1 的比 val2 要大
if ($res === 0 && $key == $count - 1) {
// 当前字段相等且已经没有下一字段可供比较，返回true
// 这里可以返回其他值，供调用方判断，减少一位元素的移动，以提高性能，变成稳定的排序
return true;
}elseif (($sorts[$index] == SORT_ASC && $res == 1) || ($sorts[$index] == SORT_DESC && $res == -1)) {
return false;
}elseif (($sorts[$index] == SORT_ASC && $res == -1) || ($sorts[$index] == SORT_DESC && $res == 1)) {
return true;
}elseif ($res === 0 && $key < $count - 1) {
// 当前字段相等则比较下一字段
return self::recurseCompare($var1, $var2, $fields, $sorts, ++$index);
}
}
// 数字排序
if ($key == $count - 1 && $var1[$key] == $var2[$key]) {
// 与上面同理
return true;
}elseif ($sorts[$index] == SORT_ASC && $var1[$key] > $var2[$key]) {
return false;
}elseif ($sorts[$index] == SORT_DESC && $var1[$key] < $var2[$key]) {
return false;
}elseif ($sorts[$index] == SORT_ASC && $var1[$key] < $var2[$key]) {
return true;
}elseif ($sorts[$index] == SORT_DESC && $var1[$key] > $var2[$key]) {
return true;
}elseif ($count - 1 > $index && $var1[$key] == $var2[$key]) {
// 与上面同理
return self::recurseCompare($var1, $var2, $fields, $sorts, ++$index);
}
}
下面送上字典排序方法（实际上就是比较ASCII码，想到更好方法的小伙伴可以在下面留言）：
/**
* [dictCompare 比较两个字符串的字典顺序]
* @param [string] $str1 [字符串1]
* @param [string] $str2 [字符串2]
* @return [type] [description]
*/
public static function dictCompare($str1, $str2) {
if (!is_string($str1) || !is_string($str2)) {
return false;
}
if ($str1 == $str2) {
return 0;
}
$len1 = strlen($str1);
$len2 = strlen($str2);
$maxlen = $len1>$len2?$len1:$len2;
for ($i = 0; $i < $maxlen; ++$i) {
if (!isset($str1[$i])) {
return -1;
}elseif (!isset($str2[$i])) {
return 1;
}
$asc1 = ord($str1[$i]);
$asc2 = ord($str2[$i]);
if ($asc1 > $asc2) {
return 1;
}elseif ($asc1 < $asc2) {
return -1;
}
}
}
这期的代码和文字有点多，但是算法的时间复杂度大O是n2，空间复杂度估计不是很高吧，适合数据量不大的情况，把顺序搜索法换成二分法搜索估计时间复杂度会降低不少，也能处理多一点的数据。另外如果字符串比较的方法能够改进一下的话，那这个算法就比较通用了。
