JS常见简单算法排序

更新日期: 2020-05-06阅读: 2.2k标签: 算法

我们面试中经常会遇到排序算法问题,我整理了冒泡排序、选择排序、插入插排等常见简单排序方法。希望此文想对了解排序的前端同学有所帮助。


封装排序数组

为了简单高效演示算法的实现思路,我先封装一个构造函数。以下排序我们默认都是从小到大排序,因为不论从大到小或者从小到大思路都一样。

function ArrayList() {
    // 创建排序数组
    this.list = [6, 3, 8, 5, 4, 1, 9, 7];
    // 排序结果以 - 分割展示
    this.toString = function () {
      return this.list.join('-')
    }
    // 交换数组 m 和 n 的位置
    this.swap = function (m, n) {
      var temp = this.list[n];
      this.list[n] = this.list[m];
      this.list[m] = temp;
    }
  }

冒泡排序

冒泡排序是依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。

  ArrayList.prototype.bubblesort = function () {
    // 第一个元素和第二个元素互换,大的放在后面, 9放最后面 [6, 3, 8, 5, 4, 1, 9, 7] => [3, 6, 5, 4, 1, 8, 7, 9]
    // 除了最后一个元素9,接着比较大小互换位置  [3, 6, 5, 4, 1, 8, 7, 9] =>  [3, 5, 4, 1, 6, 7, 8, 9]
    // 除了最后一个元素9和倒二个元素8,接着比较大小互换位置 [3, 5, 4, 1, 6, 7, 8, 9] => [3, 4, 1, 5, 6, 7, 8, 9]
    // 以此类推...   [3, 4, 1, 5, 6, 7, 8, 9] =>  [3, 1, 4, 5, 6, 7, 8, 9]
    var len = this.list.length;
    for (var j = len - 1; j >= 0; j--) {
      for (var i = 0; i < j; i++) {
        if (this.list[i] > this.list[i + 1]) {
          this.swap(i, i + 1);
        }
      }
    }
    return this.toString(); // 1-3-4-5-6-7-8-9
  }

冒泡排序的比较次数是 1 + 2 +3 + ... + N - 1 = N(N - 1)/2,大O表示法为O(N^2)。如果每两次比较交换一次那么冒泡排序的交换次数为 N(N - 1)/4。


选择排序

首先在未排序序列中找到最小元素,存放到排序序列的起始位置,再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。

  ArrayList.prototype.selectsort = function () {
    // 遍历一轮找到最小元素1,他的下标为5,下标0和下标5对换位置  [6, 3, 8, 5, 4, 1, 9, 7] =>  [1, 3, 8, 5, 4, 6, 9, 7]
    // 再从第二个元素开始遍历,找到最小值,互换位置   [1, 3, 8, 5, 4, 6, 9, 7] =>  [1, 3, 8, 5, 4, 6, 9, 7]
    // 以此类推...   [1, 3, 8, 5, 4, 6, 9, 7] =>  [1, 3, 4, 5, 8, 6, 9, 7]
    var len = this.list.length;
    for (var j = 0; j < len - 1; j++) {
      var min = j;
      for (var i = j; i < len - 1; i++) {
        if (this.list[min] > this.list[i + 1]) {
          min = i + 1;
        }
      }
      this.swap(min, j);
    }
    return this.toString(); // 1-3-4-5-6-7-8-9
  }

选择排序的比较次数是 N - 1 + N - 2 + N - 3 + ... + 1 = N*(N - 1)/2, 大O表示法为O(N^2)。 但是交换次数为 N - 1,比冒泡排序少很多。


插入排序

插入排序将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当是未排序序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。

 ArrayList.prototype.insertsort = function () {
    // 获取第二个元素3,和第一个元素6对比,3比6小,交换位置  [6, 3, 8, 5, 4, 1, 9, 7] => [3, 6, 8, 5, 4, 1, 9, 7]
    // 获取第三个元素8,8 比前面两个元素 6 和 3 都大 所有位置不变 [3, 6, 8, 5, 4, 1, 9, 7] => [3, 6, 8, 5, 4, 1, 9, 7]
    // 以此类推...  [3, 6, 8, 5, 4, 1, 9, 7] => [3, 5, 6, 8, 4, 1, 9, 7]
    var len = this.list.length;
    for (var i = 1; i < len; ++i) {
      var j = i, temp = this.list[j];
      while (this.list[j - 1] > temp && j > 0) {
        this.list[j] = this.list[j - 1];
        j--;
      }
      this.list[j] = temp;
    }
    return this.toString();
  }
  var list = new ArrayList(); // 1-3-4-5-6-7-8-9

插入排序的比较次数是 (1 + 2 +3 + ...+ N - 1)/2 = N*(N - 1)/4。它的比较次数和冒泡排序和选择排序相比是最少的。不过用大O表示法也为O(N^2)。

以上三种只是简单排序,而插入排序思想是高级排序实现的基础,后期更新介绍希尔排序和快速排序等高级排序内容。


链接: https://www.fly63.com/article/detial/8851

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!