对一个包含 a-z,A-Z以及数字的数组进行排序，最终排序后结果为小写字母，数字，大写字母的数组。

[CodeRookie262]

假设我们现在需要对 [D,a,2,F,B,1,c,5,A,z ]进行排序，要求将其中所有小写字母都排在大写字母的前面，数字排中间，数组小写字母内部和大写字母内部以及数字不要求有序, 最终排序之后为 [a,c,z,2,1,5,D,F,B,A]。

ps: 数字也无需顺序，只需要符合在小写与大写字母之间即可

[CodeRookie262]

/**
 * 对一个包含 a-z,A-Z以及数字的数组进行排序，最终排序后结果为小写字母，数字，大写字母的数组。
 * @param {Array<String | Number>} array
 * @returns {Array<String | Number>} [...lowerCase,...number,...upperCase]
 */
// 解法一：桶排序
// 缺点：空间复杂度大
function BlendSort(array) {
  let buckets = Array(3)
      .fill(0)
      .map(() => []),
    temp = [];

  array.forEach(item => {
    if (typeof item === 'string') {
      if (item >= 'a') {
        buckets[0].push(item);
      } else {
        buckets[2].push(item);
      }
    } else {
      buckets[1].push(item);
    }
  });

  buckets.forEach(i => temp.push(...i));

  return temp;
}

// 解法二：双指针遍历
// 空间复杂度：O(1)
// 时间复杂度：O(n)
function BlendSort(array) {
  let len = array.length,
    index = 0,
    left = 0,
    right = len - 1;

  // 终止条件
  if (len <= 1) return array;

  while (index <= right) {
    if (typeof array[index] === 'number') {
      index++;
    } else if (array[index] >= 'a') {
      swap(array, index++, left++);
    } else {
      swap(array, index, right--);
    }
  }

  return array;
}

/**
 * 交换元素
 * @param {Array} array 原数组
 * @param {Number} left 索引
 * @param {Number} right 索引
 */
function swap(array, left, right) {
  if (left === right) return;
  [array[left], array[right]] = [array[right], array[left]];
}