为了方便自己也帮到更多人,所有的排序算法都会简单说一下自己的思路,并附上自己能找到的最容易理解的可视化动画。
至于为什么选择用 Javascript,则是因为我觉得 Javascript 是最方便运行和调试的,只需要复制代码粘贴到浏览器的控制台就可以了,我为所有的算法附上了测试用例,通过引入 Mocha 就可以在浏览器中显示用例的通过情况。
因此我将所有的算法都整理为 CodePen 形式的在线演示,点击下文每段代码后的「在线运行」,就可以在浏览器中直接运行所有测试用例,你如果想自己进行调试或修改,只需要点击在线演示右上角的「Edit On CodePen」,就可以 Fork 一个到自己的 CodePen 修改为自己想要的版本了。如果你也曾经跟我一样对算法感到头疼,相信这是能最大限度降低上手门槛的方法。
所有 CodePen 在线演示地址可查看 Sorting Algorithms , 以下所有算法及描述按由小到大排序。
冒泡排序应该是大多数人的入门算法了,其实个人觉得「冒泡」一词有误导之嫌,叫「交换排序」更符合实际情况。因为从字面理解「冒泡」好像是选中第一数,将其一直移动到最后,但实际上一次「冒泡」过程中,可能数组中的每个元素位置都会被改变。通过不断交换相邻元素的方式,让最大的元素排到最后,个人觉得这样更容易记忆。算法描述如下
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;
}
选择排序应该是最符合人类思维的排序方式了,算法描述也很简单
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;
}
插入排序也是非常直观的一种排序,其实和玩扑克牌抽牌的过程非常相似,牌堆相当于未排序的部分,手牌相当于已排序的部分,当我们从牌堆拿起一张牌时,会根据手牌的排序,将牌插入到相应的位置,算法描述如下
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)这个数据结构,堆是一种树形结构,普遍都采用二叉树实现。堆如果满足根节点始终是堆的最小节点,则称为最小堆(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;
}
快排体现的是分治的思想,从算法描述上来看也非常简单,但老实说以人类(至少对于我)的思维习惯来说,由于存在递归,快排的算法显得并非那么直观,特别是对于快排的原地(In Place)排序版本更是如此。建议先从简单版本开始理解,多看动画演示。快排的算法描述如下
快排的简单版本
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;
}
归并排序也是非常能提现分治思想的排序算法,同时也比较符合人的思维方式,算法描述如下,可能看描述还比较抽象,看动画演示就非常直观了。
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)));
}
原文:https://avnpc.com/pages/sorting-algorithms-by-javascript
有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法
使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。
给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。
racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。
JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题
这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!