冒泡排序

英文: Bubble Sort.

指标

时间复杂度: O(n^2).
空间复杂度: O(1).
稳定性: 稳定.

算法

对比 data[i] 和 data[i + 1] 的大小, 若顺序与排序要求的相反则交换这两个值. 从头到尾对比一遍后可以确保最后一个元素的位置是正确的.

实现

void sort(std::vector<int>& data) // 升序排序
{
  for(std::size_t i = 0; i + 1 < data.size(); i++)
    for(std::size_t j = i + 1; j < data.size(); j++)
      if(data[i] > data[j])
        std::swap(data[i], data[j]);
}

优化

当第二级循环过程中没有发生交换, 则表示全部元素已处于有序状态. 可以直接结束循环.

void bubble_sort(std::vector<int>& vec) {
    for(size_t i = 0; i < vec.size() - 1; i++) {
        bool swapped = false;
        for(size_t j = 0; j < vec.size() - i; j++) {
            if(vec[j] > vec[j + 1]) {
                std::swap(vec[j], vec[j + 1]);
                swapped = true;
            }
        }
        if(!swapped)
            break;
    }
}

Info

冒泡排序并不是看上去最简单的排序算法.

评论