JS数组排序方法

常用数组排序方法

冒泡排序（从前往后，逐一比对）

function bubbleSort(arr) {
    for (let i = 0; i < arr.length-1; i++) {
        for (let k = i+1; k < arr.length; k++) {
            console.log('---')
            if(arr[i] > arr[k]) {
                // let temp = arr[k]
                // arr[k] = arr[i]
                // arr[i] = temp
                [arr[i], arr[k]] = [arr[k], arr[i]] // ES6数组换位
            }
        }
    }
    return arr
}
console.log(bubbleSort([1,3,4,7,9,45,2,133,45,133]));

快速排序（找中间，分左右）

function quickSort(arr) {
  if (arr.length <= 1) return arr // 当数组只有一位时直接返回，若不写将出现无限递归，报错：超过最大调用堆栈大小
  let index = Math.floor(arr.length / 2) // 取数组中间位置的索引
  let temp = arr.splice(index, 1) // 截取中间值
  // 若使用temp = arr[index]， 则在for循环中加上if(temp === arr[i]) continue，这样的话就实现了去重。
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (temp > arr[i]) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat(temp, quickSort(right))
}

console.log(quickSort([1,3,4,7,9,45, 2,133,45,133,0]));

插入排序（将一个数插入到有序数组中，思路跟整理扑克牌是一样的）

function insertSort(arr) {
    for(let index = 1; index < arr.length; index++) {
      let temp = arr[index];

      let j = index;
      while(j >= 0 && temp < arr[j-1]) {
        arr[j] = arr[j-1];
        j--;
      }
      arr[j] = temp;
    }
    return arr
}
console.log(insertSort([1,3,4,7,9,45,2,133,133,0]));

ES6 sort( )排序

function arraySort(arr){
  return arr.sort((a, b) => a-b); // a-b 升序排序，b-a 降序排序
}
console.log(arraySort([1,3,4,7,9,45,2,133,133,0]));

桶排序（用空间换时间）不仅排序了还去重了，此方法不常用，浪费空间。

去重原因：
1、arr数组中的每个值变成了result数组中的索引值；
2、因为在数组中的索引值是递增的每个索引值都是独一无二的；
3、如果值一样的话在arr中后面的值给result数组赋值时将会覆盖掉前面的值，如下arr中第一个133，在result中索引值为133已经赋值了当遇到第二133时也就将其覆盖了。从而桶排序不仅排序了还去重了。

浪费空间：从上面去重原因可知arr中有最大值为133时，result数组的length就为134（因为数组下标从0开始），没有值的索引用empty空代替，如果我们要给一个数组排序时数组中有某个数值为1000时，则result的数组将要创建length为1001，故浪费空间

function bucketSort(arr) {
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    result[arr[i]] = arr[i];
  }

  arr.length = 0;// 清空数组
  for (const key in result) {
    if (result.hasOwnProperty(key)) {
      arr.push(result[key])
    }
  }
  return arr
}

console.log(bucketSort([1,3,4,7,9,45,2,133,133,0]));
// expected output: [ 0, 1, 2, 3, 4, 7, 9, 45, 133 ]

最后编辑于：2021.04.02 18:29:47