如何实现带分隔符的JS计数排序 按多段数字规则升序排列数组

实现思路 #

• 先对齐排序规则，为每个字符串提取三个整数类型的排序键：
  • 一级键（最高优先级）：取-分隔符前的4位数字，转为整数
  • 二级键（次高优先级）：取-分隔符后、:分隔符前的4位数字，转为整数
  • 三级键（最低优先级）：如果字符串包含:后缀，取后缀数字转为整数；无后缀的项统一赋值为-1，保证同前缀下无后缀项排在最前
• 计数排序本身仅支持单整数键排序，针对三级优先级场景，采用最低位优先（LSD）的多轮稳定计数排序逻辑：从优先级最低的三级键开始排序，逐轮往高优先级键排序，利用计数排序的稳定性，保证高优先级排序过程中，同键值的元素不会打乱低优先级已经排好的相对顺序
• 每轮计数排序逻辑：先统计当前轮次键的最小值、最大值确定计数数组长度，统计各键出现次数后计算前缀和得到元素放置位置，倒序遍历原数组填充结果保证排序稳定性

完整可运行代码 #

/**
 * 稳定计数排序辅助函数
 * @param {Array} arr 待排序数组
 * @param {Function} getKey 从元素中提取排序整数键的方法
 * @returns {Array} 排序后的数组
 */
function stableCountingSort(arr, getKey) {
  if (arr.length <= 1) return [...arr];
  // 遍历提取所有键，确定键值范围
  let minKey = Infinity, maxKey = -Infinity;
  const keys = arr.map(item => {
    const k = getKey(item);
    minKey = Math.min(minKey, k);
    maxKey = Math.max(maxKey, k);
    return k;
  });
  // 初始化计数数组
  const countLen = maxKey - minKey + 1;
  const count = new Array(countLen).fill(0);
  // 统计每个键的出现次数
  for (const k of keys) {
    count[k - minKey]++;
  }
  // 计算前缀和，确定元素最终放置位置
  for (let i = 1; i < countLen; i++) {
    count[i] += count[i - 1];
  }
  // 倒序遍历原数组填充结果，保证排序稳定性
  const res = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    const k = keys[i];
    const pos = count[k - minKey] - 1;
    res[pos] = arr[i];
    count[k - minKey]--;
  }
  return res;
}

// 待排序数组（已故意打乱顺序，元素为字符串格式）
const targetArr = [
  '5080-2103:01',
  '5460-1601:02',
  '5080-2002:01',
  '5460-1601',
  '5080-2102',
  '5080-2002',
  '5080-2102:01',
  '5080-2103',
  '5080-2002:02',
  '5460-1601:01'
];

// 按优先级从低到高依次执行稳定计数排序
// 1. 第一排：最低优先级的三级键
let sorted = stableCountingSort(targetArr, (item) => {
  return item.includes(':') ? Number(item.split(':')[1]) : -1;
});
// 2. 第二排：次高优先级的二级键
sorted = stableCountingSort(sorted, (item) => {
  return Number(item.split('-')[1].split(':')[0]);
});
// 3. 第三排：最高优先级的一级键
sorted = stableCountingSort(sorted, (item) => {
  return Number(item.split('-')[0]);
});

console.log('排序结果：', sorted);
// 输出顺序与给定目标样式完全一致：
// [
//   '5080-2002',
//   '5080-2002:01',
//   '5080-2002:02',
//   '5080-2102',
//   '5080-2102:01',
//   '5080-2103',
//   '5080-2103:01',
//   '5460-1601',
//   '5460-1601:01',
//   '5460-1601:02'
// ]

补充说明 #

• 计数排序的时间复杂度为O(n+k)，其中n是待排序元素数量，k是键的取值范围，针对这类固定格式的编码字符串排序，性能远高于基于比较的内置sort方法，适合大数据量排序场景
• 无冒号后缀的项三级键固定为-1，天然小于所有带后缀项的正整数键值，无需额外判断即可满足同前缀无后缀项靠前的规则
• 代码可直接运行测试，打乱任意顺序的同规则输入都能输出符合要求的升序结果

内容的提问来源于stack exchange，提问作者Apalila