冒泡排序(Bubble sort)
1. 学习内容
1.1 参考
- 《程序设计基础》第6.4节（冒泡排序法）。
1.2 概要说明
1.2.1 冒泡排序思想
- 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
- 直观表达，每一趟遍历，将一个最大的数移到序列末尾。
算法描述：
- 比较相邻的元素，如果前一个比后一个大，交换之。
- 第一趟排序第1个和第2个一对，比较与交换，随后第2个和第3个一对比较交换，这样直到倒数第2个和最后1个，将最大的数移动到最后一位。
- 第二趟将第二大的数移动至倒数第二位
- ……
- 共n-1趟后，所有的数字都排好序了。
1.3 动图演示
参考VisuAlgo sorting更多了解。
2. C++实现插入排序
#include <iostream>
using namespace std;
void bubble_sort(int arr[], int len) {
int tmp = 0;
bool swapped; //【优化版】判断当次循环有没有交换元素的标记
//注意，数组最好一个元素的索引为len-1
//
// i遍循环后，最后i个元素是排好序的。len-i个元素未排好序。
//
for (int i = 0; i < len - 1; i++) { //总共遍历len-1次
swapped = false; //【优化版】初始，没有任何交换
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
swapped = true;
}
}
if (!swapped) //【优化版】没有交换，整个数组已排好序
break;
}
}
int main() {
int arr[8] = {10, 5, 7, 11, 13, 2, 9, 6};
bubble_sort(arr, 8);
for (int i = 0; i < 8; i++) {
cout << arr[i] << " ";
}
return 0;
}