详细说明JS中的算法和数据结构中常见的排序算法

本文通过实例描述了JS中的算法和常见的数据结构排序算法。分享给大家参考，如下：

排序算法（Sort）

引言

我们通常对存储在计算机中的数据执行的两个最常见的操作是排序和搜索。自从计算机诞生以来，对计算机分类和搜索的研究从未停止过。如今，在大数据和云计算时代，对数据排序和搜索的速度和效率提出了更高的要求。因此，对于排序和搜索算法要进行特殊的数据结构设计(比如我们上次讲的二叉查找树就是其中之一)，这样才能更简洁高效地操作数据。

本文将介绍数据排序的一些基本算法和高级算法，并使用JavaScript逐一实现，让大家对计算机中常见排序算法的思想和实现有一个基本的了解，起到吸引有价值建议的作用。

关于排序算法的说明

在介绍每种算法之前，我们有必要了解一些用于评估算法优缺点的术语：

稳定：如果A在B前面，当a=b时，排序后仍不稳定：如果A在B前面，当a=b时，排序后A可能出现在B后面。

内部排序：所有的排序操作都是在内存中完成的：由于数据太大，数据放在磁盘上，可以通过磁盘和内存之间的数据传输进行排序

时间复杂度：算法执行的时间和空间复杂度：运行程序所需的内存大小

如果你想了解更多时空的复杂性，我推荐一篇文章，请戳这里

基本排序算法

基本排序算法的核心思想是将一组数据按照一定的顺序重新排序，其中一般使用一组嵌套的for循环，外循环遍历数组的每一个元素，内循环用于元素的直接比较。

1.气泡排序(气泡排序)

冒泡排序是经典算法之一，也是最慢的算法之一，因为它的实现非常容易。

冒泡排序的算法如下(升序排序):

比较相邻的元素。如果第一个比第二个大，就换两个；对每对相邻的元素做同样的工作，从开始的第一对到结束的最后一对，这样最后的最大数被切换到最后一个位置，除了最后一个元素，重复以上步骤，对所有元素重复步骤1~3，直到排序完成。我就借用网上的一张动图来展示冒泡排序的过程：

冒泡排序

具体的JS实现如下：

//冒泡排序函数冒泡排序(数据){ vartemp=0；for(var I=data . length；I 0；I-){ for(var j=0；j I-1；j){ if(data[j]data[j 1]){ temp=data[j]；data[j]=data[j 1]；数据[j 1]=温度；} } }返回数据；}我们先设置了一组数据，后面会用这组数据来测试：

var dataStore=[ 72，1，68，95，75，54，58，10，35，6，28，45，69，13，88，99，24，28，30，31，78，2，77，82，72]；Console.log('原始数据： ' DatastorE)；console . log(' bubble sort : ' bubble sort(Datastore))；//原始数据：72、1、68、95、75、54、58、10、35、6、28、45、69、13、88、99、24、28、30、31、78、2、77、82

选择性排序是一种简单直观的排序算法。它的算法思想是从数组的开始遍历，将第一个元素与其他元素进行比较，记录最小的元素，循环结束后将最小的元素放在数组的第一个位置，然后从数组的第二个位置继续执行上述步骤。当我们到达数组的倒数第二个位置时，所有的数据都被排序。

选择排序也会使用嵌套循环，外循环会从数组的第一个位置移动到倒数第二个位置；内部循环从数组的第二个位置移动到最后一个位置，寻找比当前外部循环所指向的元素小的元素，并在每个内部循环结束后将最小值放在适当的位置。

同样，我在网上借了一张动态图片，展示了选择排序的过程：

选择排序

知道了算法思路，具体实现应该不成问题：

//选择排序函数selection sort(data){ for(var I=0；一.数据.长度；I){ var min=data[I]；变化的温度；var指数=I；for(var j=I ^ 1；j数据.长度；j){ if(data[j]min){ min=data[j]；index=j；} } temp=data[I]；数据[i]=最小值；数据[索引]=temp；}返回数据；}其测试结果如下：

Console.log('原始数据： ' DatastorE)；console . log(' selection sort : ' selection start(DatastorE))；//原始数据：72、1、68、95、75、54、58、10、35、6、28、45、69、13、88、99、24、28、30、31、78、2、77、82

插入排序有点像人类按字母顺序排序数据，就像玩扑克一样，把摸过的扑克按大小放在合适的位置。其原理是通过嵌套循环，外循环逐个移动数组元素，而内循环将外循环中选择的元素与其后面的元素进行比较；如果外环中的选定元素小于内环中的选定元素，数组元素将向右移动，为内环中的该元素腾出空间。

实施步骤如下：

从第一个元素开始，默认情况下，这个元素已经被排序以取出下一个元素。在排序的元素序列中从后向前扫描。如果此元素(已排序)大于新元素，将其移动到下一个位置，并重复步骤3，直到已排序的元素小于或等于新元素。将新元素插入该位置，重复步骤2~5，直到排序完成。其实现效果图如下：

插入排序

具体实现代码如下：

//插入排序函数insertionsort(data){ varlen=data . length；for(var I=1；我透镜；I){ var key=data[I]；var j=I-1；while(j=0 data[j]key){ data[j 1]=data[j]；j-；} data[j 1]=key；}返回数据；}排序结果如下：

Console.log('原始数据： ' DatastorE)；console . log(' insert sort : ' insertionSort(dataStore))；//原始数据：72，1，68，95，75，54，58，10，35，6，28，45，69，13，88，99，24，28，30，31，78，2，77，82 77，78，82，88，95，99我们学习了三种基本的排序算法，其中冒泡排序最慢，插入排序最快。我们可以通过运行过程中的console.time('sortName ')和console.timeEnd('sortName ')看到它们的效率有多高。我在这里给出一组值供参考

排序时间比较

高级排序算法

4.希尔排序(壳排序)

我们首先需要学习的是Hill排序，也叫收缩增量排序。该算法在插入排序的基础上做了很大的改进。与插入排序不同，它首先比较远处的元素，而不是相邻的元素。这种方案可以使远离正确位置的元素快速返回到合适的位置。算法遍历时，所有元素之间的距离会不断减小，直到数据结束，此时会比较相邻的元素。

这种方法的基本思想是：首先将待排列元素的整个序列分成若干个子序列(由以一定“增量”分隔的元素组成)进行直接插入和排序，然后将增量依次缩小再排序。当整个序列中的元素基本上是有序的(增量足够小)时，所有元素直接插入并排序一次。因为在元素基本有序(接近最佳情况)的情况下，直接插入排序的效率非常高，所以Hill排序的时间效率大大提高。

好的，我用一个案例来解释，会更清楚。让我们以下面这组数据为例：

数据集

Gap (increment)=10/2=5第一次按照下面的分组得到五组数据(49，13)，(38，27)，(65，49)，(97，55)，(26，4)，然后(13，49)，

第一次分组

此时，数据将按以下结构排列

第一次排序

第二次Gap=5/2=2，此时，可以得到如下两组

第二组

在组内排序后，您可以获得

二次分拣

第三次Gap=2/2=1，即排序后不分组

第三次排序

第四次Gap=1/2=0，可以得到排序后的数组

分类完成

现在，我可能对Hill排序有了一定的了解，通过JS实现如下：

//hill排序函数应为sort(array){ var increment=array . length；不同的温度；//Scratch do {//设置增量增量=数学。下限(增量/3)1；for (i=增量；i array.lengthI){ if(array[I]array[I-increment]){ temp=array[I]；for (var j=i -增量；j=0 temp数组[j]；j -=增量){ array[j increment]=array[j]；}数组[j增量]=temp；} } } while(递增1)返回数组；}效果如下：

Console.log('原始数据： ' DatastorE)；console . log(' hill sort : ' shall sort(DatastorE))；//原始数据：72、1、68、95、75、54、58、10、35、6、28、45、69、13、88、99、24、28、30、31、78、2、77、82

将两个有序序列合并成一个有序序列称为“合并”。合并和排序的思想是将一系列已排序的子序列合并成一个大的、完整的有序序列。

实施步骤如下：

将长度为n的输入序列分成长度为n/2的两个子序列；将两个子序列分别合并排序；将两个排序后的子序列合并成一个最终排序序列和一个移动图，以说明合并和排序的过程；

合并分类

具体的JS代码实现如下：

//合并排序函数merge sort(array){ var len=array . length；if(len 2 ){返回数组；} var middle=Math.floor(len/2)，left=array.slice(0，中间)，right=array.slice(中间)；返回合并(合并排序(左)，合并排序(右))；}函数合并(左，右){ var result=[]；while(left . length right . length){ if(left[0]=right[0]){ result . push(left . shift())；} else { result . push(right . shift())；} } while(left . length)result . push(left . shift())；while(right . length)result . push(right . shift())；返回结果；}测试结果如下：

Console.log('原始数据： ' DatastorE)；console . log(' hill sort : ' merge sort(dataStore))；//原始数据：72、1、68、95、75、54、58、10、35、6、28、45、69、13、88、99、24、28、30、31、78、2、77、82

快速排序是处理大数据最快的排序算法之一。这也是一个各个击破的算法。通过递归地将数据分解成包含较小元素和较大元素的不同子序列，这一步骤将被重复，直到所有序列都按顺序排列。最后，这些子序列被拼接在一起一次，以获得排序的数据。

首先，算法从序列中选择一个元素作为轴心。那么所有的数据都将围绕这个基数进行，小于改变后的基数的元素将放在它的左侧，大于或等于它的所有数字将放在它的右侧。对左右小数列重复上述步骤，直到每个区间只有一个数字。

整个分拣过程如下：

快速排序

具体实现如下：

//快速排序功能快速排序(arr) {if (arr。length==0){ return[]；} var left=[]；var right=[]；var pivot=arr[0]；for(var I=1；一、长度；I){ if(arr[I]pivot){ left . push(arr[I])；} else { right . push(arr[I])；} }返回快速排序(左)。concat(透视、快速排序(右))；}测试结果如下：

Console.log('原始数据： ' DatastorE)；console . log(' quick sort : ' quick sort(DatastorE))；//原始数据：72，1，68，95，75，54，58，10，35，6，28，45，69，13，88，99，24，28，30，31，78，2，77，82 77，78，82，88，95，99到目前为止，我们已经基本介绍了一些常用排序算法的思路和具体实现(之前的文章中已经介绍过基数排序)。排序算法博大精深，不仅要学习理论，还要不断实践。来啊！

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun来测试上述代码的运行效果。

PS:这里推荐一个排序的演示工具，供大家参考：

在线动画演示插入/选择/冒泡/合并/希尔/快速排序过程工具：http://tools.jb51.net/aideddesign/paixu_ys

更多对JavaScript相关内容感兴趣的读者可以查看本网站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》、《JavaScript错误与调试技巧总结》和0103010

希望本文对JavaScript编程有所帮助。