概念
冒泡排序（Bubble Sort）:重复地循环要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。循环数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
原理
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数或者是最小的。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
例子为从小到大排序,
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |
第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 |4 | 1 | 5 | 9 |
交换后状态| 2 | 6 |4 | 1 | 5 | 9 |
第二次两两比较,6 > 4交换
交换前状态| 2| 6 | 4 |1 | 5 | 9 |
交换后状态| 2| 4 | 6 |1 | 5 | 9 |
第三次两两比较,6 > 1交换
交换前状态| 2 | 4| 6 | 1 |5 | 9 |
交换后状态| 2 | 4| 1 | 6 |5 | 9 |
第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1| 6 | 5 |9 |
交换后状态| 2 | 4 | 1| 5 | 6 |9 |
第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5| 6 | 9 |
交换后状态| 2 | 4 | 1 | 5| 6 | 9 |
第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 |1 | 5 | 6 | 9 |
交换后状态| 2 | 4 |1 | 5 | 6 | 9 |
第二次两两比较,4 > 1交换
交换前状态| 2| 4 | 1 |5 | 6 | 9 |
交换后状态| 2| 1 | 4 |5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换前状态| 2 | 1| 4 | 5 |6 | 9 |
交换后状态| 2 | 1| 4 | 5 |6 | 9 |
第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4| 5 | 6 |9 |
交换后状态| 2 | 1 | 4| 5 | 6 |9 |
第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 |4 | 5 | 6 | 9 |
交换后状态| 1 | 2 |4 | 5 | 6 | 9 |
第二次两两比较,2 < 4不交换
交换后状态| 1| 2 | 4 |5 | 6 | 9 |
交换后状态| 1| 2 | 4 |5 | 6 | 9 |
第三次两两比较,4 < 5不交换
交换后状态| 1 | 2| 4 | 5 |6 | 9 |
交换后状态| 1 | 2| 4 | 5 |6 | 9 |
第四趟排序(外循环)无交换
第五趟排序(外循环)无交换
排序完毕,输出最终结果1 2 4 5 6 9
算法描述(C语言)
void bubble_sort(int *a, int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n -1 - i; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
int main() {
int number[] = {6, 5, 1, 7, 8, 9, 5};
int len = sizeof(number)/sizeof(int);
bubble_sort(number, len);
for (int i = 0; i < len; i++) {
printf("%d", number[i]);
}
printf("\n");
return 0;
}
算法稳定性
两个相等的元素(不管是相邻还是不相邻),排序结束后都不会发生未知交换,所以冒泡排序是****稳定****的排序算法。
算法分析
时间复杂度：最坏:O(n²) 最好：O(n-1)
