javascript排序之选择排序和插入排序，以及性能比较

昨天讲了javascript冒泡排序=>一篇文章搞定javascript冒泡排序
我们知道冒泡是通过两层for循环，对相邻的两个元素进行比较，将最大（小）值，移动到两端（左或者右），就像冒泡一样，效率的确不怎么高，今天我们要说的是选择排序，选择排序的效率同样，也不怎么高😂😂😂

选择排序

基本原理：
首先从原始数组中找到最小的元素，并把该元素放在数组的最前面，然后再从剩下的元素中寻找最小的元素，放在之前最小元素的后面，直到排序完毕。
昨天我们准备了一组长度是100的数组arr，今天我们继续使用,
还是那个🌰：

    let arr = []

    function arrData(num) {
      for (let i = 0; i < num; i++) {
        arr[i] = Math.floor(Math.random() * num + 1)
      }
    }
    arrData(100)

    function selectSort(myArr) {
      let minIndex, temp;
      for (let i = 0; i < myArr.length - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < myArr.length; j++) {
          if (myArr[j] < myArr[minIndex]) {
              //寻找最小值的索引
            minIndex = j;
          }
        //将当前（第i次查找）查找到的最小值 myArr[minIndex]和当前值（myArr[i]）位置互换
    //minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。
      [myArr[i], myArr[minIndex]]=[ myArr[minIndex],myArr[i]]
      }
      return myArr;
    }
    console.log(selectSort(arr));

输出毫无意外的：

minIndex始终保存着最小值的位置的索引，随着i的自增，遍历的数组长度越来越短，直到完成排序。
我们看下选择排序的执行过程

var arr = [65, 39, 28, 11, 10, 3];
function selectSort(myArr) {
    let minIndex, temp;
    var len=myArr.length;
    for (let i = 0; i < myArr.length - 1; i++) {
        console.log(`第${i}次`);
        minIndex = i;
        for (let j = i + 1; j < myArr.length; j++) {
            if (myArr[j] < myArr[minIndex]) {
                minIndex = j;
            }
            console.log(arr);
        }
        [myArr[i], myArr[minIndex]]=[ myArr[minIndex],myArr[i]]
    }

    return myArr;
}
console.log(selectSort(arr));

看下输出，好眼熟：

所以我们说冒泡排序和选择排序在执行效率上好像是相同的。他们真的是一样快吗？稍后讨论，我们先看一下插入排序

插入排序

有个解释很形象：

插入排序类似于人类按数字或字母顺序进行排序，例如，让班里的每个学生上交一张写有他的名字，学生证号以及个人简介的索引卡片。学生交上来的卡片是没有顺序的，但是我想让这些卡片按照字母顺序排好，这样就可以很容易的和班级花名册进行对照了。
我将卡片带回办公室，清理好书桌，然后拿起第一张卡片，卡片上的姓氏是Smith，我把它放在桌子的左上角，然后再拿起第二种卡片，这张卡片的姓氏是Brown，我把Smith向右移动，把Brown放在Smith的前面，下一张卡片是Williams，我把它放在桌子的最右边，不用移动其他卡片，下一张卡片是Acklin，这张卡片必须放在这些卡片的最前面，所以其他卡片要向右移动一个位置来为Acklin腾出位置，这就是插入排序的原理

再举一个🌰：
一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较，拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

一张很形象的图片：

总结一下插入排序的原理：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

一个🌰：

var arr = [65, 39, 28, 11, 10, 3];
function selectSort(myArr) {
    let temp, j;
    for (let i = 1; i < myArr.length; i++) {
        temp = myArr[i];
        j = i;
        while (j > 0 && myArr[j - 1] > temp) {
            myArr[j] = myArr[j - 1];
            j--;
        }
        myArr[j] = temp;
    }
    return  myArr
}
console.log(selectSort(arr));

三个排序算法的计时比较

我们讲过了三个排序

• 冒泡排序
• 选择排序
• 插入排序

现在们感受一下他们的执行效率。
arr的长度分别为10，100，1000，10000
有个技能我们需要先介绍一下

console.time()和console.timeEnd()

这两个方法中都可以传人一个参数，作为计时器的名称，它的作用是在代码并行运行时分清楚各个计时器。对console.timeEnd的调用会立即输出执行总共消耗的时间，单位是毫秒。

   let arr = []

    function arrData(num) {
      for (let i = 0; i < num; i++) {
        arr[i] = Math.floor(Math.random() * num + 1)
      }
    }
    arrData(10)

    function jssort(myArr) {
      console.time(`${myArr.length}长度冒泡排序耗时`)
      for (let i = 0; i < myArr.length - 1; i++) { //要循环多少次
        for (let j = 0; j < myArr.length - 1; j++) { //要移动几次
          if (myArr[j] > myArr[j + 1]) {
            [myArr[j], myArr[j + 1]] = [myArr[j + 1], myArr[j]]
          }
        }
      }
      console.timeEnd(`${myArr.length}长度冒泡排序耗时`)
      return myArr;
    }

    function selectSort(myArr) {
      console.time(`${myArr.length}长度选择排序耗时`)
      let minIndex, temp;
      var len = myArr.length;
      for (let i = 0; i < myArr.length - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < myArr.length; j++) {
          if (myArr[j] < myArr[minIndex]) {
            minIndex = j;
          }
        }
        [myArr[i], myArr[minIndex]] = [myArr[minIndex], myArr[i]]
      }
      console.timeEnd(`${myArr.length}长度选择排序耗时`)
      return myArr;
    }

    function insertSort(myArr) {
      console.time(`${myArr.length}长度插入排序耗时`)
      let temp, j;
      for (let i = 1; i < myArr.length; i++) {
        temp = myArr[i];
        j = i;
        while (j > 0 && myArr[j - 1] > temp) {
          myArr[j] = myArr[j - 1];
          j--;
        }
        myArr[j] = temp;
      }
      console.timeEnd(`${myArr.length}长度插入排序耗时`)
      return myArr
    }
    jssort(arr)
    selectSort(arr)
    insertSort(arr)

当长度为10：

当长度为100：

当长度为1000：

当长度为10000：

似乎可以得出一个结论，冒泡排序是最慢的，插入排序是最快的