JavaScript 中的冒泡排序

什么是冒泡排序？

排序是将给定数组打乱成升序或降序的技术。有各种技术或算法可用于对数组进行排序，例如冒泡排序、插入排序、归并排序、快速排序、基数排序等。

冒泡排序是最流行的排序算法。我们给定一个整数数组，我们必须使用冒泡排序算法对给定数组进行排序。

算法

在该算法中，我们创建两个相邻元素的“气泡”，并将此气泡从数组的开头移动到结尾。

我们将整个过程最多执行 n 次，其中 n 是数组中元素的总数。

在该算法中，我们将比较两个相邻元素，如果较小索引值大于较大索引值，那么我们将交换这两个值并移动到接下来的两个相邻值。

在数组的一次遍历中，我们将一个最大元素放到其正确位置。因此，最多需要 n 次遍历或 n 次比较迭代。

例如

在上面的例子中

对于 i=0

对于 j=0

arr[j]

对于 j=1

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [5,3,6,1,2,4]

对于 j=2

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [5,3,1,6,2,4]

对于 j=3

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [5,3,1,2,6,4]

对于 j=4

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [5,3,1,2,4,6]

i=0 后，数组为 [5,3,1,2,4,6]

现在对于 i=1

对于 j=0

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [3,5,1,2,4,6]

对于 j=1

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [3,1,5,2,4,6]

对于 j=2

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [3,1,2,5,4,6]

对于 j=3

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [3,1,2,4,5,6]

对于 j=4

arr[j]

i=1 后，数组为 = [3,1,2,4,5,6]

对于 i=2

对于 j=0

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [1,3,2,4,5,6]

对于 j=1

arr[j]>arr[j+1]，因此我们将交换这些值，数组 = [1,2,3,4,5,6]

对于 j=2

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=3

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=4

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

i=2 后，数组为 = [1,2,3,4,5,6]

对于 i=3

对于 j=0

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=1

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=2

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=3

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=4

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

i=3 后，数组为 = [1,2,3,4,5,6]

对于 i=4

对于 j=0

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=1

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=2

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=3

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=4

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

i=4 后，数组为 = [1,2,3,4,5,6]

对于 i=5

对于 j=0

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=1

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=2

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=3

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

对于 j=4

arr[j]>arr[j+1]，因此不交换，数组 = [1,2,3,4,5,6]

Javascript 代码

输出

时间复杂度： O(N²)，其中 N 是数组中元素的总数。

空间复杂度：O(1)

注意：如果数组已经排序，我们应该检查是否需要进一步迭代。如果复杂度增加，我们可以降低它。

例如，i=2 后数组已排序，我们检查到 i=5，这增加了我们的复杂度。因此，我们将使用标志变量来降低时间复杂度并减少迭代次数。

Javascript 代码

输出

时间复杂度：O(N²)，其中 N 是数组中元素的总数。

空间复杂度：O(1)

注意：如果对于任何 i，交换次数为零，则表示数组已排序，因此我们将中断循环。