javascript常见经典算法的详细说明

阅读目录

冒泡排序插入排序山丘排序合并排序快速排序选择排序奇偶排序汇总

前言：在前端百科看到这句话，以便互相鼓励。基础决定你能达到的高度，业务决定你的最低瓶颈

其实javascript算法在普通编码中用处不大，但并不妨碍我们学习它，学习这些算法的思想，锻炼自己的思维模式。

本文不会介绍每一种方法，只介绍七种方法，纯粹是为了学习。如果代码不容易理解，可以将数组的内容替换到函数中。

但是刚开始了解的时候，真的很头疼。别废话了，起来！

冒泡排序

原则：

从第一个元素开始，稍后比较，遇到比自己小的元素时交换位置

(来自百度图片)

特点：

交易所数量最多，所以它的表现最差

代码实现：

函数bubbleSort(arr){ var len=arr . length；for(var I=0；伊琳；I){ for(var j=0；jlen-1-I；J ){ if(arr[j]arr[j 1]){ //对相邻元素的比较var temp=arr[j 1]；//交互位置，所以大的放在后面arr[j ^ 1]=arr[j]；arr[j]=温度；} } }返回arr}var arr=[2，3，6，4，2，1，90，100，20，5]；console . log(Bubblesort(arr))；//[1，2，2，3，4，5，6，20，90，100]插入排序

原则：

插入排序的基本操作是将一个数据插入到有序数据中，从而得到一个数字加1的新的有序数据

如图所示

在插入排序中，数组分为两种类型：“有序数组块”和“无序数组块”。

在第一遍中，从“无序数组块”中提取20作为有序数组块。

在第二遍中，从“无序数组块”中提取一个60的数字，并将其放入“有序数组块”中，即20，60。

在第三遍中，情况也是如此，只是10的值小于有序数组的值，所以20，60的位置向后移动，为10留出插入的空间。

然后，按照这个规则，所有的插入都可以完成。

下面是一张gif图片

特点：

插入算法将待排序的数组分成两部分：

第一部分包含这个数组的所有元素，除了第一个元素(让数组多一个空间来放置插入位置)。

第二部分只包含这一个元素(即要插入的元素)。第一部分排序后，将最后一个元素插入排序后的第一部分

比气泡排序快一点

代码实现：

//插入排序//假设当前元素之前的元素已经排序完毕，先清空它们的位置，//然后比自己大的元素依次向后移动，直到空出一个‘坑’。//然后将目标元素插入“坑”中。函数insert short(arr){//从第二个元素开始，因为应该为(var i=1 iarr.lengthI){ var x=arr[I]；for(var j=I-1；arr[j]x；j-){//移出位置。arr[j 1]=arr[j]；} if(arr[j 1]！=x){ arr[j 1]=x；} }返回arr}var arr=[2，3，6，4，2，1，90，100，20，5]；console.log(insertSort(arr，2))；//[1，2，2，3，4，5，6，20，90，100]希尔排序

原则：

希尔排序，也叫下降增量排序算法，是插入排序的进化版。

什么是递减增量？它意味着定义一个区间序列，例如，5，3，1。第一次将处理所有间隔为5的数据。

下一次将处理间隔为3的元素，上一次将处理间隔为1的元素。也就是说，相邻的元素执行标准的插入排序。

步骤如下：

1.取一个小于n的整数d1作为第一个增量，将文件的所有记录分成d1组。

2.距离为d1倍数的所有记录都放在同一个组中，并在每个组中直接插入和排序。

3.取第二个增量d2d1重复上述分组和排序，

4.直到增量DT=1(dtdtdtdt-L…d2d 1)，即所有记录都放在同一个组中直接插入和排序。

这里的增量如下：

第一个增量取为：d=count/2；

第二个增量的值是：d=(count/2)/2；

最后直到：d=1；

上图观察到的现象是：

d=3时：比较40和50，因为50大，不交换。

20和30比较，因为30大，不要交换。

对比80和60，因为60小，交换。

d=2时：40和60比较，不交换，60和30交换。此时，交换的30比之前的40小，需要用30交换40，如上所示。

20和50不交换比较，50和80不交换继续比较。

当d=1时：这是前面提到的插入排序，但此时序列几乎是有序的，这给插入排序带来了很大的性能提升。

特点：

因为多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但是在不同的插入排序过程中，

同样的元素在插入排序中可能会移动，最后会干扰其稳定性，所以壳排序是不稳定的。

比如我原来的数组是[5，4，3，2，1]，所以当它受到干扰的时候，就会重新排列。

代码实现：

函数shellSort(arr){ var gap=math . floor(arr . length/2)；while(gap 0){ for(var I=gap；长度；I){ temp=arr[I]；for(var j=I；j=gap arr[j-gap]温度；j-=gap){ arr[j]=arr[j-gap]；} arr[j]=temp；} gap=Math . floor(gap/2)；}返回arr}var arr=[2，3，6，4，2，1，90，100，20，5]；console . log(shellSort(arr))；//[1，2，2，3，4，5，6，20，90，100]合并和排序

原则：

合并排序法是将两个(或多个)有序表合并成一个新的有序表，即把要排序的序列分成若干个子序列，并对每个子序列进行排序。然后有序子序列被合并成一个整体有序序列。

有几个步骤：

1.将长度为n输入序列分成长度为n/2的两个子序列；

2.继续将这两个子序列划分为m/2个子序列，并继续划分

3.将两个排序的子序列组合成最终排序的序列。

让我们有一个静态的图片，这更容易理解

这里需要补充的是，合并中数组的划分是自上而下的，合并中数组的比较是自下而上的。

特点：

速度仅次于快速排序，是一种稳定的排序算法，一般用于整体无序但子项相对有序的序列。

属于分治的思想，递归合并

代码实现：

/*排序和合并*/函数合并(左，右){ var re=[]；while(left . length 0 right . length 0){ if(left[0]right[0]){//如果左边的数据小于右边的数据，取出左边的数据放入新数组。} else { re . push(right . shift())；}}/*当左右数组长度不等时，比较后链接剩余数组项*/return re。concat(左)。concat(右)；}函数merge sort(arr){ if(arr . length==1){ return arr；}/*首先，将无序数组分成两个数组*/varmid=math。地板(arr。长度/2)；var left=arr.slice(0，中)；var right=arr.slice(中)；/*分别递归排序合并左右数组*/返回合并(mergesort(左)、mergesort(右))；}var arr=[2，3，6，4，2，1，90，100，20，5]；console . log(merge sort(arr))；//[1，2，2，3，4，5，6，20，90，100]快速排序

原则：

1.在数据集中，选择一个元素作为“轴心”。例如，选择下面的数字45

2.所有小于“基准”的元素都移动到“基准”的左侧；所有大于基准的元素都移动到基准的右侧。

3.对“基准”的左右子集重复步骤1和步骤2，直到所有子集只剩下一个元素。

特点：速度最快。与合并排序不同的是，合并排序是先分成两组再继续排列，而快速排序是分开并排排列

代码实现：

//有三个步骤：//1。找到基准(通常基于中期)。//2.遍历数组，放在左边，放在右边//3，放在右边。递归函数quickSort(arr){ //如果数组=1，返回If(arr . length=1){ return arr；} var Pivotindex=Math . floor(arr . length/2)；//找到基准并将其从原始数组中删除。var pivot=arr.split (pivot index，1)[0]；//定义左右数组var left=[]；var right=[]；//小于基准的放在左边，大于基准的放在右边(var I=0；长度；I){ if(arr[I]=pivot){ left . push(arr[I])；} else { right . push(arr[I])；} }//递归返回快速排序(左)。concat ([pivot]，快速排序(右))；} var arr=[2，3，6，4，2，1，90，100，20，5]；console . log(quick sort(arr))；//[1，2，2，3，4，5，6，20，90，100]选择排序

原理：从一组要排序的数字中，选择最小的数字与第一个位置的数字交换，然后从剩余的数字中找出最小的数字与第二个位置的数字交换，然后循环直到倒数第二个数字和最后一个数字。

静态图：

特点：可以说是冒泡排序的衍生，效率比较一般

代码实现：

//选择无序区域中最小的元素，然后将其位置与无序区域中的第一个元素交换。函数select sort(arr){ length=arr . length；for(var I=0；一、长度；I ){ //循环数组var _ min=arr[I]；//每次记录数组中的数字。var k=I；//记录(var j=I ^ 1)的指数；j长度；J ){ //如果(_min arr[j])，{ //如果当前数字大于下一个数字，_ min=arr[j]；//就说保存了下面的值，k=j；///保存索引} } arr[k]=arr[I]；//交换位置arr[I]=_ min；}返回arr}var arr=[2，3，6，4，2，1，90，100，20，5]；console . log(select sort(arr))；//[1，2，2，3，4，5，6，20，90，100]奇偶排序

原则：

选择所有奇数列并与右侧相邻元素进行比较，对前面较小的元素进行排序；

选择偶数序列的所有元素与右侧的相邻元素进行比较，对前面较小的元素进行排序；

重复前两个步骤，直到所有序列都按顺序排列。

如下图所示：

Gif图：

特点：奇偶序列交替比较

代码实现：

函数oddevensort (arr) {//swapped用于控制循环是否应该继续。如果左边的比右边的小，循环将退出，并返回排列好的数组varswapped=true。var k=0；while(swaped){ if(k0){ swaped=false；} for(var I=k；iarr . length-1；I=2){ if(arr[i]arr[i 1]){ //如果左边的数字大于右边的数字，他们交换位置arr [I]=[arr [I 1]，arr[I 1]=arr[I]][0]；swaped=true} } k=[1，0][k]；//奇数和偶数之间的变化}返回arr} var arr=[2，3，6，4，2，1，90，100，20，5]；console . log(OddeveNSORT(arr))；//[1，2，2，3，4，5，6，20，90，100]摘要

本文只总结了算法的一部分。算法的本质在于他们的想法，这在js中应该不是很有用。如果你第一次看不懂那些代码，你可以试着自己打出来。总结的时候会遇到看不懂的代码，自己打完之后理解会加深。

了解之后，确实这些算法的实现思路是广泛而深刻的，所以我们要去感受前人思想的深度。

以上就是本文的全部内容。希望本文的内容能给大家的学习或工作带来一些帮助，也希望多多支持我们！