常用排序算法

 

语雀入口

https://www.yuque.com/along-n3gko/ezt5z9

冒泡排序

    • 比较相邻的两个元素,如果前一个比后一个大,则交换位置。
    • 比较完第一轮的时候,最后一个元素是最大的元素。
    • 这时候最后一个元素是最大的,所以最后一个元素就不需要参与比较大小。
let arr = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999];
  let sortArr = (arr) => {
    let temp = null;
    for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
        }
      }
    }
    return arr;
  }

sort排序

    • arrayObject(sortby) 默认是按照字符串UniCode编码排序

字符串排序

let next = [‘a‘, ‘c‘, ‘g‘, ‘h‘, ‘b‘, ‘e‘];

next.sort();

// [‘a‘, ‘b‘, ‘c‘, ‘e‘, ‘g‘, ‘h‘ ]

升序,sort方法接受一个函数作为参数,参数传递两个参数,即返回一个a-b小于0的值,为升序

let arr2 = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999];
  let sortArr2 = (arr) => {
    return arr.sort((a, b) => {
      return a - b
    })
  }

降序,sort方法接受一个函数作为参数,参数传递两个参数,即返回一个a-b大于0的值,为降序

let arr3 = [1, 5, 8, 22, 66, 55, 0, 1, 22, 4, 88, 999];
  let sortArr3 = (arr) => {
    return arr.sort((a, b) => {
      return b - a
    })
  }

数组值为对象排序方法同上

let arr6 = [
    { ‘id‘: ‘1‘ },
    { ‘id‘: ‘2‘ },
    { ‘id‘: ‘5‘ },
    { ‘id‘: ‘100‘ },
    { ‘id‘: ‘101‘ },
    { ‘id‘: ‘31‘ },
    { ‘id‘: ‘11‘ }
  ]
  let sortArr6 = (arr) => {
    return arr.sort((a, b) => {
      return a.id - b.id
    })
  }

取最小值

Math中的min方法实现

let arr4 = [1, 5, 8, 22, 66, 55, 1, 22, 4, 88, 999];
  let sortArr4 = (arr) => {
    return Math.min(...arr);
  }

排序法:对数组进行升序或者降序排列,然后取出数组的第一个值或者最后一个值,即可取出最小值。

假设法:假设数组的第一个值是最小值,然后数组的每个元素和第一个值做比较,如果小于第一个值,则把值传递给第一个。

let a = [10,2,3,4,5,6,7,8];
var min = a[0];

for(let i=0; i<a.length; i++) {
    a[i] < min ? min = a[i] : null;
}

取最大值

Math中的max方法实现

let arr4 = [1, 5, 8, 22, 66, 55, 1, 22, 4, 88, 999];
  let sortArr4 = (arr) => {
    return Math.max(...arr);
}

排序法:对数组进行升序或者降序排列,然后取出数组的第一个值或者最后一个值,即可取出最大值。

比较法:取第一个值与所有值作比较,大于所有值则返回第一个值,否者返回大于它的那个值。

let a = [2,10,2,3,4,5,6,7,8];
const getMax = function (array){
    var max = undefined;
    for (var i = 0; i < array.length; ++i) {
      max = max === undefined ? array[i] : (max >= array[i] ? max : array[i]);
    }
    return max;
}

乱序

使用sort方法

let a = [1,2,3,4,5,6,7,8];

a.sort(() => {
    return Math.random() - 0.5
})
 

弊端:允许多次的时候就会发现末尾大值的概率高,开头小值概率高。

原来,在Chrome v8引擎源码中,处理sort方法时,使用了插入排序和快速排序两种方案。当目标数组长度小于10时,使用插入排序;反之,使用快速排序和插入排序的混合排序。

const arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]
function shuffle(arr) {
  return arr.sort(() => (Math.random() - 0.5))
}

let resultArr = Array(10).fill(0)
for (let i = 0; i < 10000; i++) {
  // sort 会改变原数组,必须用新数组来进行乱序
  let newArr = [].concat(arr)
  const tmp = shuffle(newArr)
  resultArr.forEach((item, index) => {
    // 不能直接改变 item 的值, item += tmp[index], 因为 forEach 不会改变原数组
    resultArr[index] += tmp[index]
  })
}
console.log(resultArr)
const average = resultArr.map(i => i/ 10000)
console.log(average)

// => [48544, 48860, 55333, 56927, 56797, 53396, 53790, 56762, 58967, 60624]
// => [4.8544, 4.886, 5.5333, 5.6927, 5.6797, 5.3396, 5.379, 5.6762, 5.8967, 6.0624]

洗牌算法

先从数组末尾开始,选取最后一个元素,与数组中随机一个位置的元素交换位置;然后在已经排好的最后一个元素以外的位置中,随机产生一个位置,让该位置元素与倒数第二个元素进行交换

function shuffle(a) {
    for (let i = a.length; i; i--) {
        let j = Math.floor(Math.random() * i);
        [a[i - 1], a[j]] = [a[j], a[i - 1]];
    }
    return a;
}

测试下看效果
const arr = [1, 2, 3, 4, 5, 6 ,7, 8, 9, 10]
function shuffle(a) {
    for (let i = a.length; i; i--) {
        let j = Math.floor(Math.random() * i);
        [a[i - 1], a[j]] = [a[j], a[i - 1]];
    }
    return a;
}

let resultArr = Array(10).fill(0)
for (let i = 0; i < 10000; i++) {
  // sort 会改变原数组,必须用新数组来进行乱序
  let newArr = [].concat(arr)
  const tmp = shuffle(newArr)
  resultArr.forEach((item, index) => {
    // 不能直接改变 item 的值, item += tmp[index], 因为 forEach 不会改变原数组
    resultArr[index] += tmp[index]
  })
}
console.log(resultArr)
const average = resultArr.map(i => i/ 10000)
console.log(average)

// => [55070, 54854, 54588, 55169, 55458, 54670, 55311, 54944, 55030, 54906]
// =>  [5.507, 5.4854, 5.4588, 5.5169, 5.5458, 5.467, 5.5311, 5.4944, 5.503, 5.4906]

插入排序

    • 从第二位(当前元素)开始从后向前查找
    • 若新元素(当前元素的前面)大于当前元素,将新元素移到下一位置
    • 重复2,直到在有序区找到大于或等于新元素的位置
    • 将当前元素插到上面找到的位置
    • 重复2~4
function insertionSort(arr){
    var 
        len = arr.length,
        i = 1,
        j,
        buffer;

    for (; i < len; i++) {
        buffer = arr[i];

        //在当前元素从后向前遍历,
        //一旦找到比当前元素大的就进行“元素加位”
        for (j = i - 1; j >= 0 && arr[j] > buffer; j--) {
                arr[j+1] = arr[j];
        }
        //找到的位置替换为当前元素,比它大的在上面已经“加位”了
        arr[j+1] = buffer;
    }
    
    return arr;
}

...