javascript中排序算法大全

互联网 2021/4/8 12:38:22 次

标签： javascript 排序 let const 大全 length arr orderLeft orderRight

javascript当中存在两个API：sort和indexOf来实现排序和搜索，但知其然还要知其所以然，下面来看下javascript如何实现排序和搜索算法。排序算法 1.冒泡排序时间复杂度：O(n^2). Array.prototype.bubbleSort = function () {for (let i = 0; i < this.length - 1; i+…

javascript当中存在两个API：sort和indexOf来实现排序和搜索，但知其然还要知其所以然，下面来看下javascript如何实现排序和搜索算法。

排序算法

1.冒泡排序
时间复杂度：O(n^2).

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

var arr = [3, 2, 4, 9, 1];
arr.bubbleSort();
console.log(arr);

2.选择排序
时间复杂度：O(n^2).

Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    let indexMin = i;
    for (let j = i; j < this.length - 1; j++) {
      if (this[j] < this[indexMin]) {
        indexMin = j;
      }
    }
    const temp = this[i];
    this[i] = this[indexMin];
    this[indexMin] = temp;
  }
};

const arr = [3, 4, 1, 2, 5];
arr.selectionSort();
console.log(arr);

3.插入排序
时间复杂度：O(n^2).

Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i++) {
    let temp = this[i];
    let j = i;
    //进行插入
    while (j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1];
      } else {
        break;
      }
      j--;
    }
    this[j] = temp;
  }
};

const arr = [3, 4, 1, 2, 5];
arr.insertionSort();
console.log(arr);

4.归并排序
分的时间复杂度是O(logN)
合的时间复杂度是O(n)
时间复杂度：O(n*logN)

Array.prototype.mergeSort = function () {
  const rec = (arr) => {
    //递归判断条件
    if (arr.length === 1) {
      return arr;
    }
    //先分数组
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid, arr.length);
    const orderLeft = rec(left);
    const orderRight = rec(right);
    const res = [];
    //再治数组
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        res.push(
          orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift(),
        );
      } else if (orderLeft.length) {
        res.push(orderLeft.shift());
      } else if (orderRight.length) {
        res.push(orderRight.shift());
      }
    }
    //数组合并
    return res;
  };
  const res = rec(this);
  res.forEach((n, i) => {
    this[i] = n;
  });
};

var arr = [3, 2, 4, 9, 1];
arr.mergeSort();
console.log(arr);

关于找一找教程网

本站文章仅代表作者观点，不代表本站立场，所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章，希望广大程序员努力学习，让我们用科技改变世界。
[javascript中排序算法大全]http://www.zyiz.net/tech/detail-153795.html

您可能感兴趣的文章:

上一篇：回溯算法一：算法介绍与经典问题分析

下一篇：Java编程入门与应用 P100—例4-8 （使用split（）方法对字符串进行分割）

共有条评论网友评论

关注微信小程序

扫描二维码或查找【程序员编程王】

可以随时随地学编程啦！

技术文章导航更多>

javascript中排序算法大全

排序算法

关于找一找教程网

您可能感兴趣的文章:

相关文章

共有条评论网友评论

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

javascript中排序算法大全

排序算法

关于找一找教程网

您可能感兴趣的文章:

共有 条评论 网友评论

共有条评论网友评论