javascript数据结构与算法 --- 基本排序算法

wangdai 发布于2019-08-26 11:33 / 1874人阅读

摘要：基本排序算法总结前言随着的兴起将推向的一个前所未有的高度作为为建立高性能的服务端而创建的运行平台随着时间的推移和生态链的完善已经不再局部于服务端包括前端后端桌面这篇文章介绍的传统的散打排序方法并用实现其功能如有需要可以对其封装在随后会介绍高

基本排序算法总结 前言

随着node的兴起, 将javascript推向的一个前所未有的高度, node作为为建立高性能的服务端而创建的js运行平台随着时间的推移和生态链的完善已经不再局部于服务端,包括前端,后端,桌面,这篇文章介绍的传统的散打排序方法,并用javascript实现其功能,如有需要可以对其封装,在随后会介绍高级排序算法---(希尔排序,归并排序,快速排序),下面给出链接

高级排序算法 https://segmentfault.com

冒泡排序

冒泡排序是最常见的一种排序方法,他采用类似于逐轮沉淀的方法每次找到队列中的最大值并放置与最后, 在每轮中使前一个元素与后一个元素比较,如果前者与后者就交换次序,如下图所示.

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

1 可以采用es6最新的解构语法交换数据
    [array[j+1], array[j]] = [array[j], array[j+1]];
2 为引入变量的交换 
    array[j] = array[j] + array[j+1];
    array[j+1] =  array[j] - array[j+1];
    array[j] =  array[j] - array[j+1];

选择排序

    function selectionSort(array) {
      for (let i = 0; i < array.length - 1; i++) {
        for (let j = i+1; j < array.length; j++) {
          if (array[i] > array[j]) {
            // es6
            [array[j], array[i]] = [array[i], array[j]];
          } 
        }     
      }
      return array 
    }

插入排序

    function insertionSort(array) {
      for (let i = 1; i < array.length; i++) {
        let temp = array[i];
        let j = 0;
        for (j = i - 1; (j >= 0) && (temp < array[j]); j--) {
          array[j + 1] = array[j];  
        }
        array[j + 1] = temp;
        console.log(array);
      }
      return array;
    }

实验对比

创建随机生成数组：

    let CArray = (function(params) {
      function CArray(numElements) {
        this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        this.insert = insert;
        this.toString = toString;
        this.clear = clear;
        this.setData = setData;
        this.swap = swap;
      
        for (var i = 0; i < numElements; ++i) {
           this.dataStore[i] = i;
        }
      }
      
      function setData() {
        for (var i = 0; i < this.numElements; ++i) {
           this.dataStore[i] = Math.floor(Math.random() * 
                               (this.numElements+1));
        }
      }
      
      function clear() {
        for (var i = 0; i < this.dataStore.length; ++i) {
           this.dataStore[i] = 0;
        }
      }
      
      function insert(element) {
        this.dataStore[this.pos++] = element;
      }
      
      function toString() {
        var retstr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
           retstr += this.dataStore[i] + " ";
           if (i > 0 && i % 10 == 0) {
              retstr += "
";
           }
        }
        return retstr;
      }
      
      function swap(arr, index1, index2) {
        var temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
      }
      return CArray;  
      
    })()

结论：

    var numElements = 10000;
    var myNums = new CArray(numElements);
    myNums.setData();
    
    var start = new Date().getTime();
    bubbleSort(myNums.dataStore).toString()
    var stop = new Date().getTime();
    var between = stop - start;
    console.log("冒泡排序执行时间:" + between);
    
    start = new Date().getTime();
    selectionSort(myNums.dataStore).toString()
    stop = new Date().getTime();
    between = stop - start;
    console.log("选择排序执行时间:" + between);
    
    
    start = new Date().getTime();
    insertionSort(myNums.dataStore).toString()
    stop = new Date().getTime();
    between = stop - start;
    console.log("插入排序执行时间:" + between);
    console.log(new Date().getTime());

可知对于执行效率: 选择排序 > 插入排序要 > 冒泡
排序快，插入排序是这三种算法中最快的

GPU云服务器云服务器算法与数据结构数据结构与算法排序算法图解排序算法总结

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107115.html

优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...

cheukyin 2019-08-26 10:17 评论0 收藏0
Deep in JS - 收藏集 - 掘金

摘要：今天同学去面试，做了两道面试题全部做错了，发过来给道典型的面试题前端掘金在界中，开发人员的需求量一直居高不下。排序算法 -- JavaScript 标准参考教程（alpha） - 前端 - 掘金来自《JavaScript 标准参考教程（alpha）》，by 阮一峰目录冒泡排序简介算法实现选择排序简介算法实现 ... 图例详解那道 setTimeout 与循环闭包的经典面...

enali 2019-08-20 16:36 评论0 收藏0
Javascript的数据结构与算法(四)

摘要：快速排序，参考排序算法的完整实现各种排序算法的完整实现如下冒泡排序选择排序插入排序归并排序快速排序，参考排序方法验证冒泡排序选择排序插入排序归并排序快速排序源码地址的数据结构与算法三源码 1 排序和搜索算法 1.1 排序算法 1.1.1 冒泡排序冒泡排序比较任何两个相邻的项,如果第一个比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。冒泡...

高胜山 2019-08-21 11:24 评论0 收藏0
JavaScript 版各大排序算法

摘要：推荐一下，，这里还有个可视化的排序博客，各大排序算法的实现都栩栩如生。堆排序堆排序是指利用堆这种数据结构所设计的一种排序算法。共勉参考维基百科排序搜索聊一聊排序算法秒杀种排序算法版排序图解排序算法实现欢迎来我的博客交流最近看到了很多公司都在准备明年的实习校招，虽然离三月份还有一段时间，感觉已经可以准备了。在网上看了一些排序算法和数组去重操作，感觉都写的很好，心血来潮，也来写一写。 s...

FrozenMap 2019-08-20 13:47 评论0 收藏0
排序算法回顾（JavaScript）

摘要：回顾选择排序，插入排序，冒泡排序，快速排序，希尔排序，归并排序，堆排序以及如何计算时间复杂度学习文章同学的描述数据结构等同学的十大经典算法本文代码也上传到了排序算法回顾。但希尔排序是非稳定排序算法。回顾选择排序，插入排序，冒泡排序，快速排序，希尔排序，归并排序，堆排序以及如何计算时间复杂度学习文章：hahda同学的javascript描述数据结构、hustcc等同学的十大经典算法 ...

jlanglang 2019-08-22 15:31 评论0 收藏0