首页文章资源工具教程 栏目

在线工具_工作生活好帮手

打造各种简单、易用、便捷的在线工具，网友无需注册和下载安装即可使用

点击查看

六种排序算法的Js实现

更新日期: 2019-11-01阅读: 1.7k标签: 算法

本文将介绍数据排序的基本算法和高级算法。这些算法都只依赖数组来存储数据。


数组测试平台

首先我们构造一个数组测试平台类

function CArray(numElements) {
    this.dataStore = [];
    this.numElements = numElements;
    this.toString = toString;
    this.clear = clear;
    this.setData = setData;
    this.swap = swap;
}
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.numElements; ++i) {
    this.dataStore[i] = 0;
    }
}
function toString() {
    var restr = "";
    for (var i = 0; i < this.numElements; ++i) {
    restr += this.dataStore[i] + " ";
    if (i > 0 && i % 10 == 0) {
        restr += "\n";
    }
    }
    return restr;
}
function swap(arr, index1, index2) {
    var temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

使用测试平台类

var numElements = 100;
var myNums = new CArray(numElements);
myNums.setData();
console.log(myNums.toString());


基本排序算法

这些算法非常逼真地模拟了人类在现实生活中对数据的排序。


冒泡排序

它是最慢的排序算法之一，但也是一种最容易实现的排序算法。 之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

冒泡排序的代码

function bubbleSort() {
    var numElements = this.dataStore.length;
    for (var outer = numElements; outer >= 2; --outer) {
        for (var inner = 0; inner < outer - 1; ++inner) {
            if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                this.swap(this.dataStore, inner, inner + 1);
            }
        }
    }
}

排外层循环限定了未排序的范围(从numElements到2),内层循环从左侧的数据开始逐步比较交换，使得未排序范围中最大的数移动到了最右侧，外层排序范围不断缩小，直到还剩两个未排序元素时再比较交换便完成了排序


选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有数据便完成了排序。

function selectionSort() {
    var min;
    for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
        min = outer;
        for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
            if (this.dataStore[inner] < this.dataStore[min]) {
                min = inner;
            }
        }
        swap(this.dataStore, outer, min);
    }
}


插入排序

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

function insertionSort() {
    var temp, inner;
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
    temp = this.dataStore[outer];
    inner = outer;
    while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
        this.dataStore[inner] = this.dataStore[inner - 1];
        --inner;
    }
    this.dataStore[inner] = temp;
    }
}


基本排序算法的计时比较

10000个随机数测试

bubbleSort();// 100ms左右
selectionSort();// 50ms左右
insertionSort();// 27ms左右

选择排序和插入排序要比冒泡排序快，插入排序是这三种算法中最快的。


高级排序算法

希尔排序

希尔排序在插入排序的基础上做了很大的改善。它会首先比较距离较远的元素，而非相邻的元素。这样可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素了。希尔排序的工作原理是，通过定义一个间隔序列来表示排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过大部分场景算法要用到的间隔序列可以提前定义好。  

Marchin Ciura在发表的一篇论文中定义的间隔序列为：701,301,132,57,23,10,4,1。这里我们通过一个小的数据集合来看看这个算法是怎么运行的。 

function shellsort() {
    var temp;
    for (var g = 0; g < this.gaps.length; ++g) {
    for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
        temp = this.dataStore[i];
        for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
        this.dataStore[j] = this.dataStore[j - this.gaps[g]];
        }
        this.dataStore[j] = temp;
    }
    }
}

我们需要在CArray类中增加对间隔序列的定义：

this.gaps = [5,3,1];


计算动态间隔序列

Sedgewick的算法通过下面的代码片段来决定初始间隔值：

var N = this.dataStore.length;
var h = 1;
while (h < N/3) {
    h = 3 * h + 1;
}

间隔值确定好后，这个函数就可以像之前定义的shellsort()函数一样运行了，唯一的区别是，回到外循环之前的最后一条语句会计算一个新的间隔值：

h = (h-1)/3;

动态计算间隔序列的希尔排序

function shellsort1() {
    var N = this.dataStore.length;
    var h = 1;
    while (h < N/3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (var i = h; i < N; i ++) {
            for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h]; j -= h) {
                this.swap(this.dataStore, j, j - h);
            }
        }
        h = (h-1)/3;
    }
}

对于10000个随机数的排序测试：

myNums.shellsort(); // 20ms左右
myNums.shellsort1(); // 8ms左右


归并排序

归并排序把一系列排好序的子序列合并成一个大的完整有序序列。我们需要两个排好序的子数组，然后通过比较数据大小，从最小的数据开始插入，最后合并得到第三个数组。然而，在实际情况中，归并排序还有一些问题，我们需要更大的空间来合并存储两个子数组。

自底向上的归并排序 通常来讲，归并排序会使用递归的算法来实现。然而，在JavaScript中这种方式不太可行，因为递归的深度太深了。所以，我们使用一种非递归的方式来实现这个算法，这种策略称为自底向上的归并排序。 这个算法首先将数据集分解为一组只有一个元素的数组。然后通过创建一组左右子数组将它们慢慢合并起来，每次合并都保存一部分排好序的数据，直到最后剩下的这个数组所有的数据都已完美排序。  算法代码

function mergeSort() {
    var arr = this.dataStore;
    if (arr.length < 2) {
    return;
    }
    var step = 1;
    var left, right;
    while (step < arr.length) {
    left = 0;
    right = step;
    while (right + step <= arr.length) {
        this.mergeArrays(arr, left, left+step, right, right+step);
        left = right + step;
        right = left + step;
    }
    if (right < arr.length) {
        this.mergeArrays(arr, left, left+step, right, arr.length);
    }
    step *= 2;
    }
}

function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    var rightArr = new Array(stopRight - startRight + 1);
    var leftArr = new Array(stopLeft - startLeft + 1);
    k = startRight;
    for (var i = 0; i < (rightArr.length-1); ++i) {
    rightArr[i] = arr[k];
    ++k;
    }
    k = startLeft;
    for (var i = 0; i < (leftArr.length-1); ++i) {
    leftArr[i] = arr[k];
    ++k;
    }
    rightArr[rightArr.length - 1] = Infinity;
    leftArr[leftArr.length - 1] = Infinity;
    var m = 0;
    var n = 0;
    for (var k = startLeft; k < stopRight; ++k) {
    if (leftArr[m] <= rightArr[n]) {
        arr[k] = leftArr[m];
        m++;
    } else {
        arr[k] = rightArr[n];
        n++;
    }
    }
}


快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。 这个算法首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

算法伪代码

  1. 选择一个基准元素，将列表分隔成两个子序列
  2. 对列表重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值得元素放在基准值的后面
  3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2 程序如下：
function qSort(list) {
    var list;
    if (list.length == 0) {
        return [];
    }
    var lesser = [];
    var greater = [];
    var pivot = list[0];
    for (var i = 1; i < list.length; i ++) {
        if (list[i] < pivot) {
        lesser.push(list[i]);
        } else {
        greater.push(list[i]);
        }
    }
    return this.qSort(lesser).concat(pivot, this.qSort(greater));
}

在qSort函数返回前输出排序过程

console.log(lesser.concat(pivot, greater).toString());

 10000个随机数排序测试

qSort(); // 17ms左右

快速排序算法非常适用于大型数据集合；在处理小数据集时性能反而会下降。


(附)测试平台代码

<!DOCTYPE html>
<html lang="en">
<head>
</head>
<body>
  <script>
    function CArray(numElements) {
      // this.dataStore = [72, 54, 58, 30, 31, 78, 2, 77, 82, 72];
      this.dataStore = [];
      // this.dataStore = [44, 75, 23, 43, 55, 12, 64, 77 ,33];
      this.numElements = numElements;
      this.toString = toString;
      this.clear = clear;
      this.setData = setData;
      this.swap = swap;
      this.bubbleSort = bubbleSort;
      this.selectionSort = selectionSort;
      this.insertionSort = insertionSort;
      this.shellsort = shellsort;
      this.shellsort1 = shellsort1;
      this.mergeSort = mergeSort;
      this.mergeArrays = mergeArrays;
      this.qSort = qSort;
      this.gaps = [5, 3, 1];
    }
    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.numElements; ++i) {
        this.dataStore[i] = 0;
      }
    }
    function toString() {
      var restr = "";
      for (var i = 0; i < this.numElements; ++i) {
        restr += this.dataStore[i] + " ";
        if (i > 0 && i % 10 == 0) {
          restr += "\n";
        }
      }
      return restr;
    }
    function swap(arr, index1, index2) {
      var temp = arr[index1];
      arr[index1] = arr[index2];
      arr[index2] = temp;
    }
    function selectionSort() {
        var min;
        for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
            min = outer;
            for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
                if (this.dataStore[inner] < this.dataStore[min]) {
                    min = inner;
                }
            }
            swap(this.dataStore, outer, min);
        }
    }
    function bubbleSort() {
        var numElements = this.dataStore.length;
        for (var outer = numElements; outer >= 2; --outer) {
            for (var inner = 0; inner < outer - 1; ++inner) {
                if (this.dataStore[inner] > this.dataStore[inner + 1]) {
                    this.swap(this.dataStore, inner, inner + 1);
                }
            }
        }
    }
    function insertionSort() {
      var temp, inner;
      for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        temp = this.dataStore[outer];
        inner = outer;
        while (inner > 0 && (this.dataStore[inner - 1] >= temp)) {
          this.dataStore[inner] = this.dataStore[inner - 1];
          --inner;
        }
        this.dataStore[inner] = temp;
      }
    }
    function shellsort() {
      var temp;
      for (var g = 0; g < this.gaps.length; ++g) {
        for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
          temp = this.dataStore[i];
          for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
            this.dataStore[j] = this.dataStore[j - this.gaps[g]];
          }
          this.dataStore[j] = temp;
        }
      }
    }
    function shellsort1() {
      var N = this.dataStore.length;
      var h = 1;
      while (h < N/3) {
          h = 3 * h + 1;
      }
      while (h >= 1) {
          for (var i = h; i < N; i ++) {
              for (var j = i; j >= h && this.dataStore[j] < this.dataStore[j-h]; j -= h) {
                  this.swap(this.dataStore, j, j - h);
              }
          }
          h = (h-1)/3;
      }
    }
    function mergeSort() {
      var arr = this.dataStore;
      if (arr.length < 2) {
        return;
      }
      var step = 1;
      var left, right;
      while (step < arr.length) {
        left = 0;
        right = step;
        while (right + step <= arr.length) {
          this.mergeArrays(arr, left, left+step, right, right+step);
          left = right + step;
          right = left + step;
        }
        if (right < arr.length) {
          this.mergeArrays(arr, left, left+step, right, arr.length);
        }
        step *= 2;
      }
    }
    function mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
      var rightArr = new Array(stopRight - startRight + 1);
      var leftArr = new Array(stopLeft - startLeft + 1);
      k = startRight;
      for (var i = 0; i < (rightArr.length-1); ++i) {
        rightArr[i] = arr[k];
        ++k;
      }
      k = startLeft;
      for (var i = 0; i < (leftArr.length-1); ++i) {
        leftArr[i] = arr[k];
        ++k;
      }
      rightArr[rightArr.length - 1] = Infinity;
      leftArr[leftArr.length - 1] = Infinity;
      var m = 0;
      var n = 0;
      for (var k = startLeft; k < stopRight; ++k) {
        if (leftArr[m] <= rightArr[n]) {
          arr[k] = leftArr[m];
          m++;
        } else {
          arr[k] = rightArr[n];
          n++;
        }
      }
    }
    function qSort(list) {
        var list;
        if (list.length == 0) {
            return [];
        }
        var lesser = [];
        var greater = [];
        var pivot = list[0];
        for (var i = 1; i < list.length; i ++) {
          if (list[i] < pivot) {
            lesser.push(list[i]);
          } else {
            greater.push(list[i]);
          }
        }
        return this.qSort(lesser).concat(pivot, this.qSort(greater));
    }
    var numElements = 200000;
    var myNums = new CArray(numElements);
    myNums.setData();
    // console.log(myNums.toString());
    var startTime = new Date().getTime();
    // myNums.insertionSort();// 27ms左右
    // myNums.bubbleSort();// 100ms左右
    // myNums.selectionSort();// 50ms左右
    // myNums.shellsort(); // 20ms左右
    // myNums.shellsort1(); // 8ms左右
    // myNums.mergeSort(); // 9ms左右
    myNums.dataStore = myNums.qSort(myNums.dataStore); // 17ms左右
    var endTime = new Date().getTime();
    console.log('耗时: ' + (endTime - startTime) + '毫秒');
    // console.log(myNums.toString());
    
  </script>
</body>
</html>

参考《数据结构与算法JavaScript描述》


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

上一页:  网站导航的设计细节下一页:  阻止h5手机点击图片会有查看大图的功能

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时候需要进行舍去。解法：转字符串 再转数组进行操作，看到有人用四则运算+遍历反转整数。

点击更多...

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