算法基础一：冒泡排序

一、冒泡排序

1、定义

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。

冒泡排序是所有排序算法中最简单、最易实现的算法，有时也称为起泡排序算法。

使用冒泡排序算法对 n 个数据进行排序，实现思路是：从待排序序列中找出一个最大值或最小值，这样的操作执行 n-1 次，最终就可以得到一个有序序列。
 

2、过程分析

举个例子，对 {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 次”的原因。

3、代码实现

如下是用冒泡排序算法对 { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70} 完成升序排序的C语言程序：

#include <stdio.h>
//函数声明
void Bubble_sort(int arr[], int len);int main(void)
{int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };//定义一个数组int len = sizeof(arr)/ sizeof(arr[0]);//计算数组长度 = 数组总字节数/每个元素的字节数Bubble_sort(arr, len);for (int i = 0; i < len; i++){printf("%d ", arr[i]);}return 0;
}void Bubble_sort(int arr[], int len)
{for (int i = 0; i < len - 1; i++)//循环次数（n - 1）{for (int j = 0; j < len - i - 1; j++){//每次循环的两两比较元素if (arr[j] > arr[j + 1])//如果前一个数大于后一个，就把大的给往后放{int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

如下是用冒泡排序算法对 {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70} 完成升序排序的 Python 程序：

#待排序序列
list =  [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]
def Bubble_sort():#序列中有 n 个元素，就遍历 n-1 遍for i in range(len(list-1)):#从第 1 个元素开始遍历，比那里至 len(list)-1-ifor 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=" ")

二、双向冒泡排序

1、通过冒泡排序进阶：

先回忆一下普通的冒泡排序算法，比如对 {14, 33, 27, 35, 10} 进行升序排序，过程如下图所示：
 

                                                        图 1 普通的冒泡排序

从待排序序列的第一个元素开始，比较相邻元素的大小，找到最大（或最小）的元素并移动到序列的末尾。重复整个过程，最终就可以得到一个有序的序列。

双向冒泡排序算法对图 1 的排序过程进行了优化，接下来仍以 {14, 33, 27, 35, 10} 进行升序排序为例，带大家了解双向冒泡排序。

1) 最初的待排序序列是 {14, 33, 27, 35, 10}，和普通的冒泡排序一样，从第一个元素 14 向后查找，通过相邻元素的比较，找到最大的元素并移动到序列的末尾，过程如下图所示：
 

                                                        图 2 第一轮从前向后冒泡

在图 2 的基础上，待排序序列变成了 {14, 27, 33, 10}。接下来从末尾元素 10 开始向前查找，通过相邻元素的比较，找到最小的元素并移动到序列的开头。
 

                                                                图 3 第一轮从后往前冒泡

经过了第 1 步，从元素 14 向后查找，找到了最大值 35；再从元素 10 向前查找，找到了最小值 10。最终，待排序序列变成了 {14, 27, 33}。

2) 采用和第 1 步相同的方法，从 {14, 27, 33} 中的第一个元素 14 开始向后查找，通过相邻元素的对比，最终可以找到最大值 33 并移动到序列的末尾，待排序序列变成了 {14, 27}。
 

                                                        图 4 第二轮从前往后冒泡

继续从 {14, 27} 中最后一个元素 27 开始向前查找，可以找到最小值 14 并移动到序列的开头，待排序序列变成了 {27}。
 

                                                                图 5 第二轮从后往前冒泡

3) 由于待排序序列 {27} 只有 1 个元素，不再需要冒泡排序，此时整个序列 {10, 14, 27, 33, 35} 就是一个升序序列。

2、代码实现

下面是使用双向冒泡排序对 { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 } 完成升序排序的C语言程序：

#include <stdio.h>// 函数声明
void bubble_sort(int arr[], int len);int main() {int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };int len = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度//insertion_sort(arr, len);  // 调用插入排序函数bubble_sort(arr, len);  // 调用插入排序函数// 打印排序后的数组for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}return 0;
}void bubble_sort(int arr[], int len)
{int i, temp;int low = 0, high = len -1;while (low < high){for (i = low; i < high;i++){if (arr[i] > arr[i + 1]){temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;}}high--;for (i = high; i > low; i--){if (arr[i] < arr[i - 1]){temp = arr[i];arr[i] = arr[i - 1];arr[i - 1] = temp;}}low++;}}

下面是使用双向冒泡排序对{ 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 } 完成升序排序的 Python 程序：

list = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]  # 定义并初始化一个列表list
def Bubble_sort():temp,i = 0,0low, high = 0,len(list) -1while low<high:for i in range (low,high):if list[i] > list[i+1]:list[i],list[i+1] = list[i+1],list[i]high-=1for i in range (high,low,-1):if list[i] < list[i-1]:list[i], list[i-1] =list[i-1],list[i]low+=1Bubble_sort()
for i in list:print(i,end = " ")