用 Javascript 写排序算法

时间: 2019-07-16阅读: 898标签: 算法

为了方便自己也帮到更多人,所有的排序算法都会简单说一下自己的思路,并附上自己能找到的最容易理解的可视化动画。

至于为什么选择用 JavaScript,则是因为我觉得 JavaScript 是最方便运行和调试的,只需要复制代码粘贴到浏览器的控制台就可以了,我为所有的算法附上了测试用例,通过引入 Mocha 就可以在浏览器中显示用例的通过情况。

因此我将所有的算法都整理为 CodePen 形式的在线演示,点击下文每段代码后的「在线运行」,就可以在浏览器中直接运行所有测试用例,你如果想自己进行调试或修改,只需要点击在线演示右上角的「Edit On CodePen」,就可以 Fork 一个到自己的 CodePen 修改为自己想要的版本了。如果你也曾经跟我一样对算法感到头疼,相信这是能最大限度降低上手门槛的方法。

所有 CodePen 在线演示地址可查看 Sorting Algorithms , 以下所有算法及描述按由小到大排序。


冒泡排序 (Bubble Sort)

冒泡排序应该是大多数人的入门算法了,其实个人觉得「冒泡」一词有误导之嫌,叫「交换排序」更符合实际情况。因为从字面理解「冒泡」好像是选中第一数,将其一直移动到最后,但实际上一次「冒泡」过程中,可能数组中的每个元素位置都会被改变。通过不断交换相邻元素的方式,让最大的元素排到最后,个人觉得这样更容易记忆。算法描述如下

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

动画演示冒泡排序

function bubbleSort(nums) {
  // 外循环:一共有 i 个元素要排序
  for (let i = 0; i < nums.length - 1; i++) {
    // 内循环:不断交换相邻元素, 终止条件 -i 是最后 i 个元素已经排好序
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        //js 中交换两个元素可以写成 [a, b] = [b, a] 来省去中间变量
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
  return nums;
}

在线运行冒泡排序

  • 最坏时间复杂度 O(n^2) 
  • 最优时间复杂度 O(n)
  • 平均时间复杂度 O(n^2) 
  • 最坏空间复杂度 O(n)


选择排序 (Selection Sort)

选择排序应该是最符合人类思维的排序方式了,算法描述也很简单

  1. 在未排序的元素中找到最小元素,存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。
  3. 以此类推,直到所有元素均排序完毕。

动画演示选择排序

function selectionSort(nums) {
  for (let i = 0; i < nums.length; i++) {
    let minIndex = i;
    let min = nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < min) {
        min = nums[j];
        minIndex = j;
      }
    }
    [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
  }
  return nums;
}

在线运行选择排序

  • 最坏时间复杂度 O(n^2) 
  • 最优时间复杂度 O(n^2) 
  • 平均时间复杂度 O(n^2) 
  • 最坏空间复杂度 O(n)


插入排序 (Insertion Sort)

插入排序也是非常直观的一种排序,其实和玩扑克牌抽牌的过程非常相似,牌堆相当于未排序的部分,手牌相当于已排序的部分,当我们从牌堆拿起一张牌时,会根据手牌的排序,将牌插入到相应的位置,算法描述如下

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤 2~5

动画演示插入排序

function insertionSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    let j = i;
    while (nums[j - 1] !== undefined && nums[j - 1] > nums[j]) {
      [nums[j - 1], nums[j]] = [nums[j], nums[j - 1]];
      j--;
    }
  }
  return nums;
}

在线运行插入排序


堆排序 (Heap Sort)

堆排序借助了堆(Heap)这个数据结构,堆是一种树形结构,普遍都采用二叉树实现。堆如果满足根节点始终是堆的最小节点,则称为最小堆(Min Heap);如果根节点始终是最大节点,则称为最大堆(Max Heap)。

在理解了堆的基础上,堆排序的算法就非常简单,先将数据构造为最小堆,由于根节点始终是当前堆中最小的元素,所以不停的取根节点就可以了。

动画演示堆排序

由于 Javascript 中并未内置堆这个数据结构,因此在代码演示中手动实现了一个,但在此不再赘述。你也可以自行引入其他第三方实现的堆。

function heapSort(nums) {
  const minHeap = new MinHeap();
  //使用数组构建堆
  minHeap.inserts(nums);
  const res = [];
  //如果堆中还有元素
  while (!minHeap.isEmpty()) {
    //取出根节点放入已排序数组的末尾
    res.push(minHeap.remove());
  }
  return res;
}

在线运行堆排序

  • 最坏时间复杂度 O(n*log(n)) 
  • 最优时间复杂度 O(n*log(n)) 
  • 平均时间复杂度 O(n*log(n)) 
  • 最坏空间复杂度 O(n)


快速排序 (Quick Sort)

快排体现的是分治的思想,从算法描述上来看也非常简单,但老实说以人类(至少对于我)的思维习惯来说,由于存在递归,快排的算法显得并非那么直观,特别是对于快排的原地(In Place)排序版本更是如此。建议先从简单版本开始理解,多看动画演示。快排的算法描述如下

  1. 挑选基准值:从数列中随机挑出一个元素(本例选择最后一个元素),称为“基准”(pivot)。
  2. 分割:所有比基准值小的元素摆在基准前面,大于等于基准值的元素摆在基准后面。
  3. 递归排序子序列:递归的将 1~2 步应用于小于基准值元素的子序列和大于基准值元素的子序列。

动画演示快速排序

快排的简单版本

function quickSort(nums) {
  if (nums.length <= 1) {
    return nums;
  }
  const pivot = nums.pop();
  const left = [];
  const right = [];
  while (nums.length > 0) {
    const n = nums.pop();
    n < pivot ? left.push(n) : right.push(n);
  } 
  return [...quickSort(left), pivot, ...quickSort(right)];
}

在线运行快速排序简单版本

快排的原地(In Place)排序版本

function partition(nums, left, right) {
  const pivot = nums[right];
  let partitionIndex = left;
  for (let i = left; i < right; i++) {
    if (nums[i] < pivot) {
      [nums[i], nums[partitionIndex]] = [nums[partitionIndex], nums[i]];
      partitionIndex++;
    }
  }
  [nums[right], nums[partitionIndex]] = [nums[partitionIndex], nums[right]];
  return partitionIndex;
}

function quickSort(nums, left, right) {
  left = left === undefined ? 0 : left;
  right = right === undefined ? nums.length - 1 : right;
  if (left >= right) {
    return nums;
  }
  
  const partitionIndex = partition(nums, left, right);
  quickSort(nums, left, partitionIndex - 1);
  quickSort(nums, partitionIndex + 1, right);
  return nums;
}

在线运行快速排序 In Place 版本

  • 最坏时间复杂度 O(n^2) 
  • 最优时间复杂度 O(n*log(n)) 
  • 平均时间复杂度 O(n*log(n)) 
  • 最坏空间复杂度 O(log(n)) 


归并排序 (Merge Sort)

归并排序也是非常能提现分治思想的排序算法,同时也比较符合人的思维方式,算法描述如下,可能看描述还比较抽象,看动画演示就非常直观了。

  1. 分割:递归地把当前序列平均分割成两半。
  2. 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。

动画演示归并排序

function merge(left, right) {
  const sorted = [];
  while (left.length && right.length) {
    let min = left[0] < right[0] ? left.shift() : right.shift();
    sorted.push(min);
  }
  return sorted.concat(left, right);
}

function mergeSort(nums) {
  if (nums.length <= 1) {
    return nums;
  }
  const mid = Math.floor(nums.length / 2);
  return merge(mergeSort(nums.slice(0, mid)), mergeSort(nums.slice(mid)));
}

在线运行归并排序

  • 最坏时间复杂度 O(n*log(n)) 
  • 最优时间复杂度 O(n*log(n)) 
  • 平均时间复杂度 O(n*log(n)) 
  • 最坏空间复杂度 O(n)
原文:https://avnpc.com/pages/sorting-algorithms-by-javascript


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: http://www.fly63.com/article/detial/4231

Js常用的算法教程

Js常用的算法教程 深度广度、冒泡选择、防抖节流等,函数在调用倒计时n时间内没有重复调用,则执行函数,不然重新倒计时

js算法_奇偶分割数组

分割一个整数数组,使得奇数在前偶数在后。 比如:给定 [1, 2, 3, 4],返回 [1, 3, 2, 4]。思路分析:排序好的数组:找到奇数进行操作。乱序的数组:使用sort方法进行排序+提取奇数

JavaScript 面试中常见算法问题详解

所谓提升,顾名思义即是 JavaScript 会将所有的声明提升到当前作用域的顶部。这也就意味着我们可以在某个变量声明前就使用该变量,不过虽然 JavaScript 会将声明提升到顶部,但是并不会执行真的初始化过程。

js数组的常用算法解析

不改变原数组,返回新数组(字符串);改变原数组;遍历方法;ES6语法Map键值对转化为数组;两个升序的数组合并成一个升序数组;数组重复问题;两个数组的交集;找出一个数组中只出现一次的数字

js算法-查找斐波纳契数列中第N个数

所谓的斐波纳契数列是指前2个数是 0 和 1 ,第 i 个数是第 i-1 个数和第i-2 个数的和。下面我们来用js获取菲波那契数列的第N个数为多少:递归、闭包+缓存、直接计算出该数列的值得数组,然后再从数组中取值 、直接使用数学表达式

js算法实现_二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

在开发页面的时候,我们有时候会遇到这种需求:在页面某个dom节点中遍历,找到目标dom节点,我们正常做法是利用选择器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),

JS中常用的排序方法

通过相邻数据元素的交换,逐步将待排序序列变为有序序列,如果前面的数据大于后面的数据,就将两值进行交换,将数据进行从小到大的排序,这样对数组的第0个数据到N-1个数据进行一次遍历后

影响计算机算法世界的十位大师

算法和程序设计技术的先驱者。Oh,God!一些国外网站这样评价他。一般说来,不知道此人的程序员是不可原谅的。其经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经

细数20世纪最伟大的10大算法

在广场上画一个边长一米的正方形,在正方形内部随意用粉笔画一个不规则的形状,现在要计算这个不规则图形的面积,怎么计算列?

点击更多...

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