JS中的算法与数据结构之常见排序(Sort)算法详

本文实例讲述了JS中的算法与数据结构之常见排序(Sort)算法。分享给大家供大家参考,具体如下:

排序算法(Sort) 引言

我们平时对计算机中存储的数据执行的两种最常见的操作就是排序和查找,对于计算机的排序和查找的研究,自计算机诞生以来就没有停止过。如今又是大数据,云计算的时代,对数据的排序和查找的速度、效率要求更高,因此要对排序和查找的算法进行专门的数据结构设计,(例如我们上一篇聊到的二叉查找树就是其中一种),以便让我们对数据的操作更加简洁高效。

这一篇我们将会介绍一些数据排序的基本算法和高级算法并利用JavaScript来逐一实现,让大伙对计算机中常见的排序算法的思想和实现有基本的了解,起到一个抛砖引玉的作用。

关于排序算法的说明

在介绍各个算法之前,我们有必要了解一下评估算法优劣的一些术语:

稳定:如果a原本在b前面,当a=b时,排序之后a仍然在b的前面 不稳定:如果a原本在b的前面,当a=b时,排序之后a可能会出现在b的后面

内排序:所有排序操作都在内存中完成 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行

时间复杂度:一个算法执行所耗费的时间 空间复杂度:运行完一个程序所需内存的大小

有想要了解更多,关于时间空间复杂度的,我推荐一篇文章,请戳这里

基本排序算法

基本排序算法的核心思想就是对一组数据按照一定的顺序重新排序,其中重排时一般都会用到一组嵌套的 for 循环,外循环会遍历数组的每一项元素,内循环则用于进行元素直接的比较。

1.冒泡排序(BubbleSort)

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

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

比较相邻的元素。如果第一个比第二个大,就交换它们两个;

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样最终最大数被交换到最后的位置

除了最后一个元素以外,针对所有的元素重复以上的步骤

重复步骤1~3,直到排序完成

下面我借用网上一张动图,来展示冒泡排序的过程:

冒泡排序

冒泡排序

具体的JS实现如下:

//冒泡排序 function bubbleSort ( data ) { var temp = 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]; data[j+1] = temp; } } } return data; }

我们先设定一组数据,后面我们将都用这组数据来测试 :

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( '冒泡排序:' + bubbleSort( 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 // 冒泡排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

2.选择排序(SelctionSort)

选择排序是一种比较简单直观的排序算法。它的算法思想是,从数组的开头开始遍历,将第一个元素和其他元素分别进行比较,记录最小的元素,等循环结束之后,将最小的元素放到数组的第一个位置上,然后从数组的第二个位置开始继续执行上述步骤。当进行到数组倒数第二个位置的时候,所有的数据就完成了排序。

选择排序同样会用到嵌套循环,外循环从数组第一个位置移到倒数第二个位置;内循环从第二个位置移动到数组最后一个位置,查找比当前外循环所指向的元素还要小的元素,每次内循环结束后,都会将最小的值放到合适的位置上。

同样,我借用网上一张动图,来展示选择排序的过程 :

选择排序

选择排序

了解了算法思想,具体实现应该也不成问题:

//选择排序 function selectionSort( data ) { for( var i = 0; i< data.length ; i++){ var min = data[i]; var temp; var index = i; for( var j = i + 1; j< data.length; j++){ if( data[j] < min ){ min = data[j]; index = j; } } temp = data[i]; data[i] = min; data[index]= temp; } return data; }

它的测试结果如下:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/61b2f90c0b78c37cb86167b48cbc9af2.html