24.把数组排成最小的数

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，
则打印出这三个数字能排成的最小数字为321323。

代码

// 思路：改变比较的方式
// 例如：要使 ['12', '23', '1'] 排成最小数字
// 步骤：1、取数组的头两项，将 12、23拼接为1223，将23、12拼接为2312，比较1223 < 2312，这表明这两项的相对位置可以确定为12 23
//      2、取数组的第0和第2项，将 12、1拼接为121，将1、12拼接为112，比较112 < 121，这表明这两项的相对位置可以确定为1 12
//      3、取数组的第1和第2项，将 23、1拼接为231，将1、23拼接为123，比较123 < 231，这表明这两项的相对位置可以确定为1 23
// 所以：11223应为这个数组排成的最小数字
// 其实，不难看出，这就是个排序问题，只不过排序的比较方式变得稍复杂了些。

/**
 * 判断a是否大于等于b
 * @param {*} a 
 * @param {*} b 
 */
function compare(a, b) {
  const m = '' + a + b
  const n = '' + b + a
  return m >= n
}

// 快排
function quickSort(arr, low, high) {
  if (low >= high)  return arr
  let i = low
  let j = high
  const temp = arr[low]
  while (i < j) {
    while (i < j && compare(arr[j], temp)) {
      j--
    }
    arr[i] = arr[j]
    while (i < j && compare(temp, arr[i])) {
      i++
    }
    arr[j] = arr[i]
  }
  arr[i] = temp
  quickSort(arr, low, i - 1)
  quickSort(arr, i + 1, high)
  return arr
}

function getMinNumber(arr) {
  return quickSort(arr, 0, arr.length - 1).join('')
}


const arr = [12, 23, 34, 123, 321, 21]

// 12123212332134
console.log( getMinNumber(arr) )