专栏首页前端杂谈前端算法-基本排序算法比较

前端算法-基本排序算法比较

基本排序算法

  这里主要介绍的基本排序算法主要包括: 冒泡排序,选择排序,插入排序,之后的文章会介绍希尔排序,快速排序等高级排序算法, 文章后面会对这几个算法进行性能比较. 基本排序算法的核心思想是对一组数据按照一定的顺序重新排列. 重新排列主要就是嵌套的for循环. 外循环会遍历数组每一项,内循环进行元素的比较. 注: 文中都以实现升序排序为例:

1.冒泡排序

  冒泡排序是最慢的排序算法之一, 也是最容易实现的排序算法.使用这种算法进行排序时,数据值会像气泡一样从数组的一端漂浮到另一端,所以称之为冒泡排序.假设要对数组按照升序排列,较大的值会浮动到数组的右侧,较小值会浮到左侧.

原理:

  从开始第一对相邻元素开始,对每一对相邻元素进行比较,如果第一个比第二个大,就交换它们两个, 这样直到最后一对元素比较结束,最后的元素就是最大的数,重复这个过程,就可以完成排序.

示意图:

代码:

      function bubbleSort(arr) {
        for (let i = 0; i < arr.length; i++) {
          for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
              let temp = arr[j];
              arr[j] = arr[j + 1];
              arr[j + 1] = temp;
            }
          }
        }
        return arr;
      }

2.选择排序

原理:

  首先找出当前元素中最小的元素,并放到排序序列的起始位置,然后再从剩余的元素中寻找最小的元素,然后放到已排序序列的末尾。以此类推,直到排序完成。

示意图:

代码:

      function selectionSort(arr) {
        var len = arr.length;
        var minIndex, temp;
        for (var i = 0; i < len - 1; i++) {
          minIndex = i;
          for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
              minIndex = j;
            }
          }
          temp = arr[i];
          arr[i] = arr[minIndex];
          arr[minIndex] = temp;
        }
        return arr;
      }

3.插入排序

原理:

  从第二个元素开始(假定第一个元素已经排序了),取出这个元素,在已经排序的元素中从后向前进行比较,如果该元素大于这个元素,就将该元素移动到下一个位置,然后继续向前进行比较,直到找到小于或者等于该元素的位置,将该元素插入到这个位置后.重复这个步骤直到排序完成.

示意图:

代码: 

      function insertionSort(arr) {
        var len = arr.length;
        var preIndex, current;
        for (var i = 1; i < len; i++) {
          preIndex = i - 1;
          current = arr[i];
          while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
          }
          arr[preIndex + 1] = current;
        }
        return arr;
      }

4.基本排序算法的性能比较

  使用console.time进行时间计算,在需要测试的开始位置写上console.time,并且括号内传一个字符串。在结束的位置使用console.timeEnd方法,并再次把字符串传入,即可在控制台查看执行时间. 首先创建一个n位随机数组用来测试.

      function createRandomArr(n) {
        let arr = [];
        for (let i = 0; i < n; i++) {
          arr.push(Math.floor((Math.random() * 100)));
        }
        return arr;
      }

分别记录3种算法所用时间:

  var testArr = createRandomArr(1000);
  //  记录冒泡排序所用时间
  console.time('bubbleSort');
  bubbleSort(testArr);
  console.timeEnd('bubbleSort');
  var testArr = createRandomArr(1000);
  //  记录选择排序所用时间
  console.time('selectionSort');
  selectionSort(testArr);
  console.timeEnd('selectionSort');
  var testArr = createRandomArr(1000);
  //  记录插入排序所用时间
  console.time('insertionSort');
  insertionSort(testArr);
  console.timeEnd('insertionSort');

在Chrome执行代码,在控制台看看他们的执行时间对比, Duang Duang Duang!

当然, 要进行多次运行, 得到的结果才能被视为有效的结论. 很显然, 插入排序比其他两种排序方法快.

注: 文中图片转自: https://www.cnblogs.com/onepixel/articles/7674659.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 怎么在vue中使用less

    用户1741436
  • 如何开发中后台项目

    工作中的你,是不是手上做着后台系统项目,应对着做不完的需求,觉得做后台系统是个没有技术含量的活,技术没法提升,这么想或许你就错了,如果能做以到以下几点,不仅可以...

    用户1741436
  • 项目中如何使用babel6详解

    用户1741436
  • 你对JavaScript的Array对象了解有多少?

    工作中,数组应用非常广泛,菜单、列表、banner图等等都会应用到数组,所以必须对数组的属性和方法非常熟练才OK,下面一起来了解一下。

    Javanx
  • linux shell数组基础

    不管数值型还是字符串型,都是用一对圆括号表示,并且数组的元素之间用空格隔开,但是字符型的元素需要加引号 比如

    Y大宽
  • 排序算法算法对比

    排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

    朱晓霞
  • Swift:数组遍历 修改数组中指定成员值 关键字 inout

    菜菜不吃蔡
  • JavaScript去除数组中重复的数字

    hankleo
  • js中数组常用逻辑算法(从大到小,从小到大排序,去重等问题)

    honey缘木鱼
  • LeetCode 1426. 数元素(哈希set)

    给你一个整数数组 arr, 对于元素 x ,只有当 x + 1 也在数组 arr 里时,才能记为 1 个数。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券