冒泡排序是所有排序算法中最简单、最易实现的算法 ， 有时也称为起泡排序算法 。
使用冒泡排序算法对 n 个数据进行排序 ， 实现思路是：从待排序序列中找出一个最大值或最小值 ， 这样的操作执行 n-1 次 ， 最终就可以得到一个有序序列 。
举个例子 ， 对 {14, 33, 27, 35, 10} 序列进行升序排序（由小到大排序） ， 冒泡排序算法的实现过程是：
● 从 {14, 33, 27, 35, 10} 中找到最大值 35；
● 从 {14,33,27,10} 中找到最大值 33；
● 从 {14, 27, 10} 中找到最大值 27；
● 从 {14, 10} 中找到最大值 14；
由此 ， 我们就得到了一个有序序列 {10, 14, 27, 33, 35} 。
那么 ， 如何从待排序序列中找到最大（或最小）的值呢？以找最大值为例 ， 遍历待排序序列 ， 过程中不断地比较相邻两个元素的值 ， 如果后者比前者的值小就交换它们的位置 。遍历完成后 ， 最后一个元素就是当前待排序序列中最大的 。
例如 ， 从 {14, 33, 27, 35, 10} 中找到最大值 35 的过程如下：
1) 比较 14 和 33 的大小 ， 显然后者更大 ， 不需要交换它们的位置 ， 序列不发生改变 。
文章插图
2) 比较 33 和 27 的大小 ， 前者大于后者 ， 交换它们的位置 ， 新的序列如下图所示 。
文章插图
3) 比较 33 和 35 的大小 ， 后者更大 ， 不需要交换它们的位置 ， 序列不发生改变 。
文章插图
4) 比较 35 和 10 的大小 ， 前者大于后者 ， 交换它们的位置 ， 新的序列如下图所示 。
文章插图
可以看到 ， 序列中值最大的元素 35 被移动到了序列的末尾 。整个查找最大值的过程中 ， 最大的元素就像水里的气泡一样 ， 一点一点地“冒”了出来 ， 这也是将该算法命名为冒泡排序算法的原因 。
采用同样的方法 ， 我们可以很轻松地从 {14, 27, 33, 10} 中找到最大值 33 。找到 33 后的新序列为：
文章插图
从 {14, 27, 10} 中找到最大值 27 后 ， 新的序列如下图所示：
文章插图
从 {14, 10} 中找到最大值 14 后 ， 新的序列如下图所示：
文章插图
所有比 10 大的数都被一一找到 ， 所以 10 必然是最小的数 ， 这也是为什么“对 n 个数据进行排序 ， 找最大值的过程只重复 n-1 次”的原因 。
冒泡排序算法的具体实现如下是冒泡排序算法实现升序排序的伪代码：
Bubble_sort(list): // list 表示待排序序列for i <- 0 to length(list)-1: // 对于元素个数为 n 的 list 序列 ， 需遍历 n-1 次 ， 这里用 [0,length(list)-1) 表示 。for j <- 1 to length(list) - i: // 从第 1 个元素开始遍历 ， 遍历区间为 [1,length(list)-i) 。if list[j] > list[j+1]: // 若进行降序排序 ， 则改成 < 小于号swap(list[j] , list[j+1]) // 交换 2 个相邻元素的位置 return list // 返回排好序的序列————————————根据伪代码 ， 冒泡排序算法的时间复杂度为O(n2) 。
如下是用冒泡排序算法对 {14, 33, 27, 35, 10} 完成升序排序的 C 语言程序：
#include<stdio.h>#define N 5 //设定待排序序列中的元素个数//实现冒泡升序排序算法的函数 ， list[N] 为待排序数组void Bubble_sort(int list[N]) { int i, j; int temp = 0; // N 个元素 ， 遍历 N-1 次for (i = 0; i < N - 1; i++) {// 从第 1 个元素开始遍历 ， 遍历至 N-1-ifor (j = 0; j < N - 1 - i; j++) {//比较 list[j] 和 list[j+1] 的大小if (list[j] > list[j + 1]) {//交换 2 个元素的位置temp = list[j];list[j] = list[j + 1];list[j + 1] = temp;}} }} int main() { int i = 0; int list[N] = { 14,33,27,35,10 };Bubble_sort(list);//输出已排好序的序列for (i = 0; i < N; i++) {printf("%d ", list[i]);} return 0;}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 大众|人人开得起！曝大众将打造全新入门级电动车
- Object JavaScript 高级入门 对象 对象 实例
- 稀疏矩阵一次定位快速转置算法
- python算法基础之贪心算法
- next permutation 算法图解：下个排列
- 翡翠|翡翠新手不知道怎么选翡翠？5大要素带你入门
- 搞数仓也得懂几个常用机器学习算法
- C 不再是一种编程语言
- 学习c语言要背哪些必备英语单词吗？
- 桶排序算法
