JavaScript 常用排序算法详解：冒泡与选择排序

说明：本文内容主要参考网络资料，代码由作者独立编写。旨在复习基础知识，非原创内容。

冒泡排序算法解析

1. 冒泡排序（Bubble Sort）

(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. 选择排序（Selection Sort）

这是一种表现稳定的排序算法，无论输入数据如何，其时间复杂度均为 O(n²)，因此适用于数据规模较小的场景。其主要优势在于无需占用额外内存空间。理论上，选择排序也是常见的排序方法之一。

（1）算法简介

选择排序是一种简单直观的排序算法。其工作原理是：在未排序序列中找到最小（或最大）元素，将其存放到排序序列的起始位置；然后从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾。以此类推，直到所有元素排序完毕。

（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]，将其与无序区的第 1 个记录 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)

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