冒泡排序
冒泡排序（Bubble Sort）
冒泡排序是最基础的交换排序。冒泡排序之所以叫冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。
按照冒泡排序的思想，要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
例如一个有8个数字组成的无序序列，进行升序排序。
普通冒泡排序：相邻比较与交换
解锁完整互动实验、进阶解析与精选参考答案。
这样一来，元素9作为数列中最大的元素，就像是汽水里的小气泡一样，浮到了最右侧。这时，冒泡排序的第1轮就结束了。数列最右侧元素9的位置可以认为是一个有序区域，有序区域目前只有1个元素。
接着进行第2轮排序。
第2轮排序结束后，数列右侧的有序区有了2个元素。
根据相同的方法，完成剩下的排序。
算法分析
冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法每一轮都要遍历尚未排定的相邻元素，共进行n - 1轮有效比较。
| 时间复杂度 | 空间复杂度 | 稳定性 | 设计思想 |
|---|---|---|---|
| 稳定 | 贪心法 |
冒泡排序
#include <stdio.h>
#include <stdbool.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Bubble Sort (original v1.0)
*/
T *bubble_sort(T *arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}逆序对
假设数组有n个元素，如果A[i] > A[j], i < j，那么A[i]和A[j]就被称为逆序对（inversion）。
#include <stdio.h>
int count_inverses(int *arr, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", count_inverses(arr, n));
return 0;
}冒泡排序第一次优化
常规的冒泡排序需要进行n - 1轮循环，即使在中途数组已经有序，但是还是会继续剩下的循环。例如当数组是{2, 1, 3, 4, 5}时，在经过一轮排序后已经变为有序状态，再进行多余的循环就会浪费时间。
为了解决这个问题，可以在每一轮循环中设置一个标志。如果该轮循环中有元素发生过交换，那么还不能仅据此判断排序已经完成。如果没有发生过交换，说明当前数组已经完成排序。
冒泡排序第一次优化
第一次优化：无交换则提前结束
解锁完整互动实验、进阶解析与精选参考答案。
#include <stdio.h>
#include <stdbool.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Bubble Sort (original v1.0)
*/
T *bubble_sort(T *arr, int n) {
for (int i = 0; i < n; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) {
break;
}
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}冒泡排序第二次优化
在经过一次优化后，算法还存在一个问题，例如数组{2, 3, 1, 4, 5, 6}在经过一轮交换后变为{2, 1, 3, 4, 5, 6}，但是在下一轮时后面有很多次比较都是多余的，因为并没有产生交换操作。
为了解决这个问题，可以再设置一个标志位，用于记录当前轮所交换的最后一个元素的下标。在下一轮排序中，只需比较到该标志位即可，因此之后的元素在上一轮中没有交换过，在这一轮中也不可能交换了。
冒泡排序第二次优化
第二次优化：记录最后交换位置
解锁完整互动实验、进阶解析与精选参考答案。
#include <stdio.h>
#include <stdbool.h>
typedef int T;
#define swap(x, y) \
{ \
T temp = x; \
x = y; \
y = temp; \
}
/**
* Bubble Sort (original v1.0)
*/
T *bubble_sort(T *arr, int n) {
int right = n - 1;
for (int i = 0; i < n; i++) {
bool swapped = false;
int last = 0;
for (int j = 0; j < right; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
last = j;
}
}
if (!swapped) {
break;
}
right = last;
}
return arr;
}
int main() {
int arr[] = {5, 8, 6, 3, 9, 2, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}知识测验
知识测验
追踪相邻交换
对[4,1,3,2]执行基本冒泡排序，写出每次相邻比较后的数组，并分别统计比较与实际交换次数。不要使用提前结束优化。