js十大算法[通俗易懂]

js十大算法[通俗易懂]JS的十大经典算法冒泡排序(BubbleSort)冒泡排序须知:作为最简单的排序算法之一,冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。。。冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。什么时候最快(BestCases):当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊。。。。)什么时候最慢…

大家好,又见面了,我是你们的朋友全栈君。

JS的十大经典算法

冒泡排序(Bubble Sort)

冒泡排序须知:

作为最简单的排序算法之一,冒泡排序给我的感觉就像Abandon在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。。。冒泡排序还有一种优化算法,就是立一个flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。。。

什么时候最快(Best Cases):

当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊。。。。)

什么时候最慢(Worst Cases):

当输入的数据是反序时(写一个for循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗。。。)

冒泡排序JavaScript代码实现:
复制代码
 1 function bubbleSort(arr) {
 2     var len = arr.length;
 3     for (var i = 0; i < len; i++) {
 4         for (var j = 0; j < len - 1 - i; j++) {
 5             if (arr[j] > arr[j+1]) {        //相邻元素两两对比
 6                 var temp = arr[j+1];        //元素交换
 7                 arr[j+1] = arr[j];
 8                 arr[j] = temp;
 9             }
10         }
11     }
12     return arr;
13 }
复制代码

选择排序(Selection Sort)

选择排序须知:

在时间复杂度上表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序JavaScript代码实现:
复制代码
 1 function selectionSort(arr) {
 2     var len = arr.length;
 3     var minIndex, temp;
 4     for (var i = 0; i < len - 1; i++) {
 5         minIndex = i;
 6         for (var j = i + 1; j < len; j++) {
 7             if (arr[j] < arr[minIndex]) {     //寻找最小的数
 8                 minIndex = j;                 //将最小数的索引保存
 9             }
10         }
11         temp = arr[i];
12         arr[i] = arr[minIndex];
13         arr[minIndex] = temp;
14     }
15     return arr;
16 }
复制代码

插入排序(Insertion Sort)

插入排序须知:

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌,那估计这辈子你对插入排序的算法都不会产生任何兴趣了。。。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。对于这种算法,得了懒癌的我就套用教科书上的一句经典的话吧:感兴趣的同学可以在课后自行研究。。。

插入排序JavaScript代码实现:
复制代码
 1 function insertionSort(arr) {
 2     var len = arr.length;
 3     var preIndex, current;
 4     for (var i = 1; i < len; i++) {
 5         preIndex = i - 1;
 6         current = arr[i];
 7         while(preIndex >= 0 && arr[preIndex] > current) {
 8             arr[preIndex+1] = arr[preIndex];
 9             preIndex--;
10         }
11         arr[preIndex+1] = current;
12     }
13     return arr;
14 }
复制代码

希尔排序(Shell Sort)

希尔排序须知:

希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。在这里,我就使用了这种方法。

希尔排序JavaScript代码实现:
复制代码
 1 function shellSort(arr) {
 2     var len = arr.length,
 3         temp,
 4         gap = 1;
 5     while(gap < len/3) {          //动态定义间隔序列
 6         gap =gap*3+1;
 7     }
 8     for (gap; gap> 0; gap = Math.floor(gap/3)) {
 9         for (var i = gap; i < len; i++) {
10             temp = arr[i];
11             for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
12                 arr[j+gap] = arr[j];
13             }
14             arr[j+gap] = temp;
15         }
16     }
17     return arr;
18 }
复制代码

归并排序(Merge Sort)

归并排序须知:

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  1. 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第2种方法)
  2. 自下而上的迭代

在《数据结构与算法JavaScript描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

However, it is not possible to do so in JavaScript, as the recursion goes too deep
for the language to handle.
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

说实话,我不太理解这句话。意思是JavaScript编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。
更新
在《JavaScript语言精粹》的第四章里提到了递归问题。对我之前的疑问进行了解答:

Some languages offer the tail recursion optimization. This means that if a function returns the result of invoking itself recursively, then the invocation is replaced with a loop, which can significantly speed things up. Unfortunately, JavaScript does not currently provide tail recursion optimization. Functions that recurse very deeply can fail by exhausting the return stack.
一些语言提供了尾递归优化。这意味着如果一个函数返回自身递归调用的结果,那么调用的过程会被替换为一个循环,它可以显著提高速度。遗憾的是,JavaScript当前并没有提供尾递归优化。深度递归的函数可能会因为堆栈溢出而运行失败。

简而言之,就是JavaScript没有对递归进行优化。运用递归函数不仅没有运行速度上的优势,还可能造成程序运行失败。因此不建议使用递归。

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。

归并排序JavaScript代码实现:
复制代码
 1 function mergeSort(arr) {  //采用自上而下的递归方法
 2     var len = arr.length;
 3     if(len < 2) {
 4         return arr;
 5     }
 6     var middle = Math.floor(len / 2),
 7         left = arr.slice(0, middle),
 8         right = arr.slice(middle);
 9     return merge(mergeSort(left), mergeSort(right));
10 }
11 
12 function merge(left, right)
13 {
14     var result = [];
15 
16     while (left.length>0 && right.length>0) {
17         if (left[0] <= right[0]) {
18             result.push(left.shift());
19         } else {
20             result.push(right.shift());
21         }
22     }
23 
24     while (left.length)
25         result.push(left.shift());
26 
27     while (right.length)
28         result.push(right.shift());
29 
30     return result;
31 }
复制代码

快速排序(Quick Sort)

快速排序须知:

又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好,可是这是为什么呢,我也不知道。。。好在我的强迫症又犯了,查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是O(n²),比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ,且O(n log n)记号中隐含的常数因子很小,比复杂度稳定等于O(n log n)的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

更新
《算法 第四版》里对于快速排序的优缺点进行了更加明确的解释:

快速排序的内循环比大多数排序算法都要短小,这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱,在实现时要非常小心才能避免低劣的性能。

快速排序JavaScript代码实现:
复制代码
 1 function quickSort(arr, left, right) {
 2     var len = arr.length,
 3         partitionIndex,
 4         left = typeof left != 'number' ? 0 : left,
 5         right = typeof right != 'number' ? len - 1 : right;
 6 
 7     if (left < right) {
 8         partitionIndex = partition(arr, left, right);
 9         quickSort(arr, left, partitionIndex-1);
10         quickSort(arr, partitionIndex+1, right);
11     }
12     return arr;
13 }
14 
15 function partition(arr, left ,right) {     //分区操作
16     var pivot = left,                      //设定基准值(pivot)
17         index = pivot + 1;
18     for (var i = index; i <= right; i++) {
19         if (arr[i] < arr[pivot]) {
20             swap(arr, i, index);
21             index++;
22         }        
23     }
24     swap(arr, pivot, index - 1);
25     return index-1;
26 }
27 
28 function swap(arr, i, j) {
29     var temp = arr[i];
30     arr[i] = arr[j];
31     arr[j] = temp;
32 }
复制代码

堆排序(Heap Sort)

堆排序须知:

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

    大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列

    小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列

堆排序JavaScript代码实现:
复制代码
 1 var len;    //因为声明的多个函数都需要数据长度,所以把len设置成为全局变量
 2 
 3 function buildMaxHeap(arr) {   //建立大顶堆
 4     len = arr.length;
 5     for (var i = Math.floor(len/2); i &gt;= 0; i--) {
 6         heapify(arr, i);
 7     }
 8 }
 9 
10 function heapify(arr, i) {     //堆调整
11     var left = 2 * i + 1,
12         right = 2 * i + 2,
13         largest = i;
14 
15     if (left < len && arr[left] > arr[largest]) {
16         largest = left;
17     }
18 
19     if (right < len && arr[right] > arr[largest]) {
20         largest = right;
21     }
22 
23     if (largest != i) {
24         swap(arr, i, largest);
25         heapify(arr, largest);
26     }
27 }
28 
29 function swap(arr, i, j) {
30     var temp = arr[i];
31     arr[i] = arr[j];
32     arr[j] = temp;
33 }
34 
35 function heapSort(arr) {
36     buildMaxHeap(arr);
37 
38     for (var i = arr.length-1; i > 0; i--) {
39         swap(arr, 0, i);
40         len--;
41         heapify(arr, 0);
42     }
43     return arr;
44 }
复制代码

计数排序(Counting Sort)

计数排序须知:

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

计数排序JavaScript代码实现:
复制代码
 1 function countingSort(arr, maxValue) {
 2     var bucket = new Array(maxValue+1),
 3         sortedIndex = 0;
 4         arrLen = arr.length,
 5         bucketLen = maxValue + 1;
 6 
 7     for (var i = 0; i < arrLen; i++) {
 8         if (!bucket[arr[i]]) {
 9             bucket[arr[i]] = 0;
10         }
11         bucket[arr[i]]++;
12     }
13 
14     for (var j = 0; j < bucketLen; j++) {
15         while(bucket[j] > 0) {
16             arr[sortedIndex++] = j;
17             bucket[j]--;
18         }
19     }
20 
21     return arr;
22 }
复制代码

桶排序(Bucket Sort)

桶排序须知:

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。
为了使桶排序更加高效,我们需要做到这两点:

  1. 在额外空间充足的情况下,尽量增大桶的数量
  2. 使用的映射函数能够将输入的N个数据均匀的分配到K个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

什么时候最快(Best Cases):

当输入的数据可以均匀的分配到每一个桶中

什么时候最慢(Worst Cases):

当输入的数据被分配到了同一个桶中

桶排序JavaScript代码实现:
复制代码
 1 function bucketSort(arr, bucketSize) {
 2     if (arr.length === 0) {
 3       return arr;
 4     }
 5 
 6     var i;
 7     var minValue = arr[0];
 8     var maxValue = arr[0];
 9     for (i = 1; i < arr.length; i++) {
10       if (arr[i] < minValue) {
11           minValue = arr[i];                //输入数据的最小值
12       } else if (arr[i] > maxValue) {
13           maxValue = arr[i];                //输入数据的最大值
14       }
15     }
16 
17     //桶的初始化
18     var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
19     bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
20     var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
21     var buckets = new Array(bucketCount);
22     for (i = 0; i < buckets.length; i++) {
23         buckets[i] = [];
24     }
25 
26     //利用映射函数将数据分配到各个桶中
27     for (i = 0; i < arr.length; i++) {
28         buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
29     }
30 
31     arr.length = 0;
32     for (i = 0; i < buckets.length; i++) {
33         insertionSort(buckets[i]);                      //对每个桶进行排序,这里使用了插入排序
34         for (var j = 0; j < buckets[i].length; j++) {
35             arr.push(buckets[i][j]);                      
36         }
37     }
38 
39     return arr;
40 }
复制代码

基数排序(Radix Sort)

基数排序须知:

基数排序有两种方法:

  1. MSD 从高位开始进行排序
  2. LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
基数排序:根据键值的每位数字来分配桶
计数排序:每个桶只存储单一键值
桶排序:每个桶存储一定范围的数值

基数排序JavaScript代码实现:
复制代码
 1 //LSD Radix Sort
 2 var counter = [];
 3 function radixSort(arr, maxDigit) {
 4     var mod = 10;
 5     var dev = 1;
 6     for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
 7         for(var j = 0; j < arr.length; j++) {
 8             var bucket = parseInt((arr[j] % mod) / dev);
 9             if(counter[bucket]==null) {
10                 counter[bucket] = [];
11             }
12             counter[bucket].push(arr[j]);
13         }
14         var pos = 0;
15         for(var j = 0; j < counter.length; j++) {
16             var value = null;
17             if(counter[j]!=null) {
18                 while ((value = counter[j].shift()) != null) {
19                       arr[pos++] = value;
20                 }
21           }
22         }
23     }
24     return arr;
25 }
复制代码

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/150193.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • smartctl命令详解_fuser命令

    smartctl命令详解_fuser命令smart用法1.smartctl-son/dev/sda”开启磁盘的smart功能2.smartctl-a/dev/sda”显示磁盘的详细smart信息3.smartctl–test=short/dev/sda4.smartctl–test=short/dev/sdb检查磁盘坏道…

  • js 除法取整数、取余数的方法

    js 除法取整数、取余数的方法**js除法取整数、取余数的方法取整1.取整//丢弃小数部分,保留整数部分parseInt(5/2)  //22.向上取整//向上取整,有小数就整数部分加1Math.ceil(5/2)  //33.向下取整//向下取整,丢弃小数部分Math.floor(5/2)  //24四舍五入//四舍五入Math.round(5/2)  //3取余//取余6%4  //**…

  • ubuntu中apt和dpkg命令总结「建议收藏」

    ubuntu中apt和dpkg命令总结「建议收藏」1.apt和dpkg命令总结apt-cachesearch#——(package搜索包)apt-cacheshow#——(package获取包的相关信息,如说明、大小、版本等)apt-getinstall#——(package安装包)apt-getinstall#—–(package–reinstall重新安装包)apt-get

  • js实现replaceAll方法

    js实现replaceAll方法js本来有replace方法,请看w3school的说明:replace()方法用于在字符串中用一些字符替换另一些字符,或替换一个与正则表达式匹配的子串。语法:stringObject.replace(regexp/substr,replacement)第一个参数为一个字符串或者一个正则表达式,第二个参数为一个字符串或者一个用于生成字符串的函数。注意重点:如果regexp…

  • 免费的UML工具

    免费的UML工具VisualParadigmCommunityEdition是自2004年以来推出的,旨在提供免费的UML软件,用于非商业目的,支持在UML建模方面迈出第一步的用户,以及需要免费的跨平台UML建模软件的用户个人使用,如在学生项目中使用UML。UML建模工具免费用于各种非商业目的。支持13个UML2.x图和ERD图。VisualParadigmCommFreeUMLToolforPersonalandnon-Commercialpurposes,downloadnow!

  • 菜鸟教程 Java 学习笔记 (基础教程)

    1、Java对象和类Java作为一种面向对象的语言,支持以下基本概念:多态、继承、封装、抽象、类、对象实例、方法、重载。对象:对象是类的一个实例,有状态和行为。类:类是一个模板,它描述一类对象的行为和状态。1.1创建对象对象是根据类创建的,在Java中,使用关键字new来创建一个新的对象。创建对象需要以下三步:(1)声明:声明一个对象,包括对象名称和对象类型。(2)实例化:使

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号