javascript基本排序算法分析

注意：大部分内容都是从网上抄来的，代码都是自己写的。从旧知识中学习不是原创。

1.冒泡排序(冒泡排序)

(1)算法描述

冒泡排序是一种简单的排序算法。它反复访问要排序的序列，一次比较两个元素，如果顺序不对就交换它们。重复访问序列，直到不需要交换，也就是说序列已经排序。这个算法的名字来源于这样一个事实，即较小的元素将通过交换慢慢“浮动”到序列的顶部。

(2)算法描述与实现

具体算法描述如下：

1.比较相邻的元素。如果第一个比第二个大，就换两个；2.对每对相邻的元素做同样的工作，从开始的第一对到结束的最后一对，这样最后一个元素应该是最大的数字；3.对除最后一个元素之外的所有元素重复上述步骤；4.重复步骤1~3，直到排序完成。

JavaScript代码的实现：

改进冒泡排序：设置一个符号变量pos，记录每次排序通过的最后一次交换位置。由于pos位置后的记录已经交换到位，因此只需在下一次分拣时扫描pos位置。

改进后的算法如下：

在传统的冒泡排序中，每次排序操作只能找到一个最大值或最小值。我们认为，在每次分拣操作中，通过使用正向和反向气泡两次，可以一次获得两个最终值(最大值和最小值)，因此分拣通过次数几乎减少了一半。

改进的算法是：

三种算法的运行时间为：

从运行结果可以看出，时间复杂度更低，耗时更短。你可以自己试试。运行时最好将三种算法写在一个文件中，否则会因为浏览器等原因出现错误。

气泡排序的动态图演示；

(3)算法分析

最优情况：T(n)=O(n)

当输入数据已经是正序列时

最坏情况：T(n)=O(n2)

当输入数据的顺序相反时

平均情况：T(n)=O(n2)

2.选择排序(选择排序)

O(n)最稳定的排序算法，因为不管什么数据进去，都是o (n)的时间复杂度……所以使用的时候，数据量越小越好。唯一的优点可能是它不占用额外的内存空间。理论上讲，选择排序也可能是大多数人平时想到的排序方式。

(1)算法介绍

Selection-sort是一种简单直观的排序算法。其工作原理：首先，在未排序的序列中找到最小(大)元素，并将其存储在排序序列的开头；然后，继续从剩余的未排序元素中搜索最小的(大的)元素，并将其放在排序序列的末尾。以此类推，直到所有元素都被排序。

(2)算法描述与实现

通过对n条记录进行n-1次直接选择性排序，可以得到有序的结果。具体算法描述如下：

1.初始状态：无序区域是r [1.n]，有序区域为空；2.在第I次排序开始时(i=1，2，3…n-1)，当前有序和无序区域为R [1.I-1]和R (I.n)，分别为。在该序列中，从当前无序区域中选择具有最小关键字的记录R[k]，并将其与无序区域中的第一个记录R交换，使得R[1.i]和R[i 1.n)分别成为记录数增加1的新有序区域和记录数减少1的新无序区域。3.n-1之旅后，阵列被订购。

Javascript代码的实现：

(3)算法分析

最佳情况：T(n)=O(n2)最差情况：T(n)=O(n2)平均情况：T(n)=O(n2)

以上就是本文的全部内容。希望对大家的学习有帮助，支持我们。