陌上寒

陌上寒个人博客

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

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

选择排序

基本原理:
首先从原始数组中找到最小的元素,并把该元素放在数组的最前面,然后再从剩下的元素中寻找最小的元素,放在之前最小元素的后面,直到排序完毕。
昨天我们准备了一组长度是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));

输出毫无意外的:
《javascript排序之选择排序和插入排序,以及性能比较》
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));

看下输出,好眼熟:
《javascript排序之选择排序和插入排序,以及性能比较》
所以我们说冒泡排序和选择排序在执行效率上好像是相同的。他们真的是一样快吗?稍后讨论,我们先看一下插入排序

插入排序

有个解释很形象:

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

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

一张很形象的图片:

《javascript排序之选择排序和插入排序,以及性能比较》

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

  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:
《javascript排序之选择排序和插入排序,以及性能比较》
当长度为100:
《javascript排序之选择排序和插入排序,以及性能比较》
当长度为1000:
《javascript排序之选择排序和插入排序,以及性能比较》
当长度为10000:
《javascript排序之选择排序和插入排序,以及性能比较》

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

发表评论

电子邮件地址不会被公开。