数组中随机取出一个元素，然后按照数组数据的本身规律将数据插回正确位置

Question

const data = [
  "node-0",
  "node-0-0",
  "node-0-1",
  "node-0-2",
  "node-0-3",
  "node-0-4",
  "node-0-5",
  "node-0-6",
  "node-0-7",
  "node-0-8",
  "node-0-9",
  "node-0-10",
  "node-0-11",
  "node-0-12",
  "node-0-13",
  "node-0-14",
  "node-0-15",
  "node-2",
  "node-3",
  "node-4",
  "node-5",
  "node-6",
  "node-8",
  "node-9",
  "node-11",
  "node-12",
  "node-14",
  "node-16",
  "node-17",
];

数组特性，

1. 元素由 "node" + index + index2 +index3 ...组成
2. 元素的顺序遵循 每个index 升序排列

特别注意

如果直接使用 sort 排序， 会产生错误情况

node-1
node-12
node-13

// ...
node-1-0

Answer 1

重点应该是比较大小和数据查找

// 比较大小
function compareValue(value1, value2) {
  const arr1 = value1.split('-');
  const arr2 = value2.split('-');
  const length = Math.max(arr1.length, arr2.length);
  let diff = 0;
  for(let i = 1; i < length; i ++) {
    const val1 = Number(arr1[i] || 0);
    const val2 = Number(arr2[i] || 0);
    diff = val1 - val2;
    if (diff != 0) {
      break;
    }
  }
  return diff;
}

// 二分查找，找索引
function binarySearch(value, start = 0, end = data.length - 1) {
  let midIndex = Math.floor((start + end) / 2);
  let midValue = data[midIndex];
  let resultIndex = start;
  if (value < data[start]) return start;
  if (value > data[end]) return end + 1;
  if (start >= end) return resultIndex;
  const diff = compareValue(midValue, value);
  if (diff == 0) {
      resultIndex = midIndex
  } else if (diff < 0) {
      start = midIndex + 1;
      resultIndex = binarySearch(value, start, end)
  } else {
      end = midIndex - 1;
      resultIndex = binarySearch(value, start, end)
  }
  return resultIndex;
}

然后测试一下

let value = 'node-1-11'
let index = binarySearch(index)
// 插入到原数组
data.splice(index, 0, value)

Answer 2

function compare(a, b) {
  const arr1 = a.split('-').slice(1);
  const arr2 = b.split('-').slice(1);
  const len = Math.max(arr1.length, arr2.length);

  for (let i = 0; i < len; i++) {
    const item1 = arr1[i] || 0;
    const item2 = arr2[i] || 0;

    if (item1 == item2) continue;

    return item1 - item2 > 0 ? 1 : -1;
  }
}

data.sort(compare)

Answer 3

只要能找出规律，就没有sort函数排序不了的数组：

function findIndex(arr, value) {
    arr = arr.concat([value]);
    arr.sort(function(a, b) {
        var lengthA = (a = a.split("-")).length;
        var lengthB = (b = b.split("-")).length;
        var length = Math.min(lengthA, lengthB);
        for (var i = 1; i < length; ++i) {
            var diff = a[i] - b[i];
            if (diff) return diff;
        }
        return lengthA - lengthB;
    });
    return arr.indexOf(value);
}
var node = "node-0-16";
var index = findIndex(data, node);
data.splice(index, 0, node);
console.dir(index); // 元素在数组中应该插入的位置
console.dir(data); // 插入元素后的数组