首页 > 代码库 > 冒泡排序算法

冒泡排序算法

冒泡排序

简介

  冒泡排序是一种简单的排序算法,属于暴力算法的一种。基本思想是通过比较相邻的元素,并将其有序化而逐步将整个序列有序化。

伪代码

  procedure bubble sort(A1, A2,....,An: 整数)

   for(i from 1 to n - 1)

    for(j from i + 1 to n) 

      if(A[i] < A[j]) then 交换两个数据

C++代码(C++14) 

void bubbleSort(auto array[], const int count)
{
    for(int i = 0; i != count - 1; ++i)
    {
        for(int j = i + 1; j != count; ++j)
        {
            if(array[i] < array[j])
            {
                auto temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
        }
    }
}

缺点

  • 需要对列表进行多次遍历,排序所需时间较长,不适合大量元素的排序
  • 当列表已经有序依然要对整个列表多次遍历。

算法复杂度

  • 由于整个列表都需要进行多次遍历比较,所以不存在最优与最坏的情况。
  • 平均算法复杂度(省略掉索引的比较)  
  •     程序第一次遍历需要N-1次比较(第一个元素与其余元素比较),第二次需要N-2次比较(第二个元素与之后的元素比较),因此算法总共需要 N-1 + N-2 + N-3 +...+ 1 = (N^2 -N)/2 次比较,因此算法复杂度为Θ(N^2)

改进

  • 对于冒泡排序而言,如果某一次遍历时未发生任何数据的交换,并且相邻的两个元素均有序,则证明列表已经有序。此时可以停止遍历。因而可以在程序中加入一个布尔变量来进行跟踪

冒泡排序算法