冒泡排序又称起泡排序,是最容易实现的一种排序算法,时间复杂度为O(n2)
。
冒泡排序算法的工作原理是:反复遍历待排序的目标序列,过程中不断比较相邻元素的值,对于违背升序或降序规则的相邻元素,互换它们的位置。直至各相邻元素不再需要互换位置,则排序结束。
此排序算法每次遍历待排序序列,都会从序列中筛选出一个最大值或者最小值,这也是将该排序算法称为“冒泡”或者“起泡”的原因。
举个例子,假设有一个待排序序列 {14,33,27,35,10},使用冒泡排序算法对其进行升序(由小到大)排序的过程如下:
1、第一次遍历整个序列:
1) 比较相邻元素 14 和 33 的值,显然 14 < 33,符合升序的要求,无需交换它们的位置,序列保持原样。
2) 继续比较相邻元素 33 和 27 的值,33 > 27,不符合升序的要求,交换它们的位置,新序列如下所示:
3) 继续比较相邻元素 33 和 35 的值,33 < 35,符合升序的要求,序列保持原样。
4) 继续比较相邻元素 35 和 10 的值,35 < 10,不符合升序的要求,交换它们的位置,新序列如下所示:
由此,从待排序序列中筛选出了最大值 35,并将其置于待排序序列的末尾。
2、第二次遍历:
待排序序列变为 {14 , 27 , 33 , 10},继续采用相同的办法遍历该序列,最终得到的新序列为:
3、第三次遍历:
待排序序列变成 {14 , 27 , 10},继续采用相同的方法遍历该序列,最终得到的新序列为:
4、第四次遍历:
待排序序列变为 {14,10},继续采用相同的方法遍历该序列,最终得到的新序列为:
至此,整个序列变为升序序列。
冒泡排序算法的具体实现
如下为冒泡排序算法实现升序排序的伪代码:
Bubble_sort(list): // list 表示待排序序列
for i <- 1 to length(list): // list 序列中有多少个元素,就遍历多少遍(最后一遍不做任何操作)
for j <- 1 to length(list) - i: // 从第 1 个元素开始遍历,遍历至第 length(list) -i 个元素
if list[j] > list[j+1]: // 若进行降序排序,则改成 < 小于号
swap(list[j] , list[j+1]) // 交换 2 个相邻元素的位置
return list // 返回排好序的序列
如下为用冒泡排序算法对 {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 次 for (i = 0; i < N; i++) { // 从第 1 个元素开始遍历,遍历至 N-1-i for (j = 0; j < N - 1 - i; j++) { //比较 list[j] 和 list[j++] 的大小 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; }
如下为用冒泡排序算法对 {14,33,27,35,10} 进行升序排序的 Java 程序:
public class Demo { public static void Bubble_sort(int[] list) { int length = list.length; // length 个元素,遍历 length 次 for (int i = 0; i < length; i++) { // 从第 1 个元素开始遍历,遍历至 length-1-i for (int j = 0; j < length - 1 - i; j++) { // 比较 list[j] 和 list[j++] 的大小 if (list[j] > list[j + 1]) { // 交换 2 个元素的位置 int temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; } } } } public static void main(String[] args) { int[] list = { 14, 33, 27, 35, 10 }; Bubble_sort(list); // 输出已排好序的序列 for (int i = 0; i < list.length; i++) { System.out.print(list[i] + " "); } } }
如下为用冒泡排序算法对 {14,33,27,35,10} 进行升序排序的 Python 程序:
#待排序序列 list = [14,33,27,35,10] def Bubble_sort(): #有多少个元素,就遍历多少遍 for i in range(len(list)): #从第 1 个元素开始遍历,比那里至 len(list)-1-i for j in range(len(list)-1-i): #比较两个相邻元素的大小 if list[j] > list[j+1]: #交换 2 个元素的位置 list[j],list[j+1] = list[j+1],list[j] Bubble_sort() for i in list: print(i,end=" ")
以上程序的执行结果均为:
10 14 27 33 35