算法-冒泡排序

发表于 更新于 分类于

算 法：冒泡排序算法
时间复杂度：$O(n^2)$

  • 冒泡排序算法概述

  • 冒泡排序伪代码

  • 冒泡排序实现

冒泡排序算法概述

冒泡排序通常是我们在学习编程的过程中遇到排序问题，最先接触到的算法，它的算法过程就是每一趟排序都会通过交换不满足排序状态的相邻两个数来达到每一趟排序都让一个元素“冒泡”到正确位置，直到最后一趟“冒泡”过程完成，也就完成了排序。

冒泡排序算法描述

  1. 第$i$趟“冒泡”过程从序列尾部遍历至第$i$个元素;
  2. 对于每一趟“冒泡”过程，比较每个正在遍历的元素与前一个元素的大小关系，如不满足，则交换2者位置;
  3. 持续1-2步骤直至对于每个位置都进行一趟“冒泡”过程为止。

冒泡排序示例

未排序： 5 31 16 7 9 10 3
第一趟： [3] 5 31 16 7 9 10
第二趟： [3 5] 7 31 16 9 10
第三趟： [3 5 7] 9 31 16 10
第四趟： [3 5 7 9] 10 31 16
第五趟： [3 5 7 9 10] 16 31
第六趟： [3 5 7 9 10 16] 31
第七趟： [3 5 7 9 10 16 31]

冒泡排序的动态演示：

VisuAlgo-排序（冒泡排序，选择排序，插入排序，归并排序，快速排序，基数排序，基数排序）

冒泡排序伪代码

（引用自《算法导论》）
BUBBLESORT(A)

1
2
3
4
for i = 1 to A.length - 1
  for j = A.length downto i + 1
    if A[j] < A[j - 1]
      exchange A[j] with A[j - 1]

冒泡排序实现

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(arrType* a, int arrLength)
{
    int i, j, t;

    for (i = 0; i < arrLength - 1; i++) {
        for (j = arrLength - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
               t = a[j];
               a[j] = a[j - 1];
               a[j - 1] = t;
            }
        }
    }
}

Pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure bubblesort;   
var
  i, j, t : integer;
begin
  for i := 1 to arrLength - 1 do
    for j := arrLength downto i + 1 do
        if a[j] < a[j - 1] then
            begin
                t := a[j];
                a[j] := a[j - 1];
                a[j - 1] := t;
            end;
end;

参考资料

  • 《算法导论》（第三版）