冒泡排序

8/17/2020 数据结构与算法基础

冒泡排序就是重复“从序列右边开始比较相邻两个数字的大小,再根据结果交换两个数字 的位置”这一操作的算法。在这个过程中,数字会像泡泡一样,慢慢从右往左“浮”到序列的 顶端,所以这个算法才被称为“冒泡排序”。

20161009190728886

# 步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

# 举例

1.对数字 1~9 进行排序 -w556

2.在序列的最右边放置一个天平,比较天平两边的数字。如果右边的数字较小,就交换这两个数字的位置。 -w521

3.由于 6 < 7,所以交换这两个数字。 -w313

4.完成后,天平往左移动一个位置,比较两个数 字的大小。此处 4 < 6,所以无须交换。

-w300

5.继续将天平往左移动一个位置并比较数字。重复同样的操作直到天平到达序列最左边为止。 -w539

6.不断对数字进行交换,天平最终到达了最左边。通过这一系列操作,序列中最小的数字就会移动到最左边。

-w551

7.最左边的数字已经归位。

-w500

8.将天平移回最右边,然后重复之前的操作,直到天平到达左边第 2 个位置为止。

-w495

9.当天平到达左边第 2 个位置时,序列中第 2 小的数字也就到达了指定位置。

-w484

10.将天平再次移回最右边,重复同样的操作直到所有数字都归位为止。

-w476

11.由于 9 > 6,所以交换这两个数字。

-w308

12.由于 9 > 8,所以交换这两个数字。 -w308

13.排序完成 -w492

# 代码

func bubleSort(_ numbers: [Int]) -> [Int] {
    var nums = numbers
    let n = nums.count
    for i in 0..<n {
        for j in 0..<(n-1-i) {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j+1)
            }
        }
    }
    return nums
}

let nums = [3, 42, 1, 5, 34, 20, 9]
bubleSort(nums)

# 性能

在冒泡排序中,第 1 轮需要比较 n-1 次,第 2 轮需要比较 n-2 次......第 n-1 轮需要比较 1 次。因此,总的比较次数为 (n - 1) + (n - 2) + ... + 1 ≈ n^2/2。这个比较次数恒定为该数值,和输入数据的排列顺序无关。

不过,交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况,如输入数据正好以从小到大的顺序排列,那么便不需要任何交换操作;反过来,输入数据要是以从大到小的顺序排列,那么每次比较数字后便都要进行交换。因此,冒泡排序的时 间复杂度为 O(n^2)。

上次更新: 6/18/2022, 10:39:15 AM