冒泡排序

排序算法的效率和数据规模有关。

排序的核心操作是比较。

数据位置交换是一种昂贵的操作，交换的总次数对于评估算法的效率很重要。

排序存在稳定与否的问题。

复杂度分析

冒泡排序的遍历次数是固定的。

以从小到大排序为例：

  • 第一遍排序，共有 $$n$$ 项数据未排序，因此需要比较 $$n - 1$$ 次
  • 第二遍排序，已经筛选出了数据的最小值，只需要再比较 $$n - 2$$ 次
  • 第 $$n - 1$$ 遍排序，只剩下最后两个元素没有排序，需要比较 $$1$$ 次

在最好的情况下，元素已经全部排序完毕，只需要进行比较、不需要进行位置交换，时间复杂度为：O(1)；

在最坏的情况下，每一次比较都伴随着位置交，时间复杂度为 1 + 2 + \cdots +(n - 1) = \frac{(1 + n - 1)(n - 1)}{2}=O(n^2)；

平均情况下，取 \frac{1}{2}\sum\limits_{i=1}^{n-1}i = O(n^2)

冒泡排序是原地排序。

冒泡排序是稳定的。已经就位的元素不会再次被调换位置。

算法

基础算法

对相邻的元素进行比较，每次都交换相对较（大）小的元素，这样子一遍排序结束后，就有一个确定的最值。

鸡尾酒算法

两边同时进行冒泡排序，从左到右采取升序、从右到左采取降序。其复杂度仍然是 O(n^2)，对冒泡排序进行了略微优化。

梳排序

冒泡排序只会比较相邻的项，而梳排序可以比较间距大于1的项。刚开始的时候设置比较间距为数组长度，然后按照 1.3 的递减率固定递减。间距为 1 时，退化为冒泡排序。时间复杂度是 O(n\log n)，空间复杂度是 O(1)，属于不稳定排序。

实现

Rust

  1. fn bubble_sort<T>(nums: &mut [T])
  2. where
  3.     T: ::std::cmp::PartialOrd,
  4. {
  5.     for i in 0..(nums.len() - 1) {
  6.         for j in (i + 1)..nums.len() {
  7.             if nums[i] > nums[j] {
  8.                 nums.swap(i, j);
  9.             }
  10.         }
  11.     }
  12. }

C++

  1. template<typename T>
  2. void bubble_sort(T nums[], int len) {
  3.     using std::swap;
  4.     for (auto i = 0; i < len - 1; i++) {
  5.         for (auto j = i + 1; j < len; j++) {
  6.             if (nums[i] > nums[j])
  7.                 swap(nums[i], nums[j]);
  8.         }
  9.     }
  10. }

Go

  1. func bubble_sort(nums []int) []int {
  2.     length := len(nums)
  3.     for i := 0; i < length-1; i++ {
  4.         for j := i; j < length; j++ {
  5.             if nums[i] > nums[j] {
  6.                 nums[i], nums[j] = nums[j], nums[i]
  7.             }
  8.         }
  9.     }
  10.     return nums
  11. }

OCaml

  1. let rec bubble_sort l =
  2.   let sorted = match l with
  3.     | hi :: hj :: t ->
  4.         if hi > hj then
  5.           hj :: bubble_sort( hi :: t)
  6.         else
  7.           hi :: bubble_sort(hj :: t)
  8.     | t -> t
  9.   in
  10.   if l = sorted then l
  11.   else bubble_sort sorted
  13. let rec print_list l =
  14.   match l with
  15.   | h :: t ->
  16.       print_int h;
  17.       print_char ' ';
  18.       print_list t
  19.   | [] -> print_char '\n'
  22. let test_l = [54; 26; 93; 17; 77; 31; 44; 55; 20];;
  24. print_list (bubble_sort test_l)