冒泡排序详解
如有错误,感谢不吝赐教、交流
文章目录
- 算法原理
- python代码实现
- Java实现
- 总结
算法原理
升序实现,反之则亦然:
1.重复遍历要排列的数列,比较相邻的元素。如果第一个比第二个大,交换
2.第一轮结束确定一个最大元素到末尾
3.针对除了最后一个元素外的所有元素重复上面步骤
python代码实现
arr = [86, 39, 77, 23, 32, 45, 58, 63, 93, 4, 37, 22] # 待排序数组# 升序实现
for i in range(len(arr)):print("开始第{}轮排序:".format(i))for j in range(i, len(arr) - 1 - i):if arr[j + 1] < arr[j]:tmp = arr[j]arr[j] = arr[j+1]arr[j+1] = tmpprint(arr) # 打印查看每一步排序后结果print("第{}排序轮后:".format(i))print(arr)
执行结果:
开始第0轮排序:
[39, 86, 77, 23, 32, 45, 58, 63, 93, 4, 37, 22]
[39, 77, 86, 23, 32, 45, 58, 63, 93, 4, 37, 22]
[39, 77, 23, 86, 32, 45, 58, 63, 93, 4, 37, 22]
[39, 77, 23, 32, 86, 45, 58, 63, 93, 4, 37, 22]
[39, 77, 23, 32, 45, 86, 58, 63, 93, 4, 37, 22]
[39, 77, 23, 32, 45, 58, 86, 63, 93, 4, 37, 22]
[39, 77, 23, 32, 45, 58, 63, 86, 93, 4, 37, 22]
[39, 77, 23, 32, 45, 58, 63, 86, 93, 4, 37, 22]
[39, 77, 23, 32, 45, 58, 63, 86, 4, 93, 37, 22]
[39, 77, 23, 32, 45, 58, 63, 86, 4, 37, 93, 22]
[39, 77, 23, 32, 45, 58, 63, 86, 4, 37, 22, 93]
第0排序轮后:
[39, 77, 23, 32, 45, 58, 63, 86, 4, 37, 22, 93]
开始第1轮排序:
[39, 23, 77, 32, 45, 58, 63, 86, 4, 37, 22, 93]
[39, 23, 32, 77, 45, 58, 63, 86, 4, 37, 22, 93]
[39, 23, 32, 45, 77, 58, 63, 86, 4, 37, 22, 93]
[39, 23, 32, 45, 58, 77, 63, 86, 4, 37, 22, 93]
[39, 23, 32, 45, 58, 63, 77, 86, 4, 37, 22, 93]
[39, 23, 32, 45, 58, 63, 77, 86, 4, 37, 22, 93]
[39, 23, 32, 45, 58, 63, 77, 4, 86, 37, 22, 93]
[39, 23, 32, 45, 58, 63, 77, 4, 37, 86, 22, 93]
[39, 23, 32, 45, 58, 63, 77, 4, 37, 22, 86, 93]
第1排序轮后:
[39, 23, 32, 45, 58, 63, 77, 4, 37, 22, 86, 93]
开始第2轮排序:
[39, 23, 32, 45, 58, 63, 77, 4, 37, 22, 86, 93]
[39, 23, 32, 45, 58, 63, 77, 4, 37, 22, 86, 93]
[39, 23, 32, 45, 58, 63, 77, 4, 37, 22, 86, 93]
[39, 23, 32, 45, 58, 63, 77, 4, 37, 22, 86, 93]
[39, 23, 32, 45, 58, 63, 4, 77, 37, 22, 86, 93]
[39, 23, 32, 45, 58, 63, 4, 37, 77, 22, 86, 93]
[39, 23, 32, 45, 58, 63, 4, 37, 22, 77, 86, 93]
第2排序轮后:
[39, 23, 32, 45, 58, 63, 4, 37, 22, 77, 86, 93]
开始第3轮排序:
[39, 23, 32, 45, 58, 63, 4, 37, 22, 77, 86, 93]
[39, 23, 32, 45, 58, 63, 4, 37, 22, 77, 86, 93]
[39, 23, 32, 45, 58, 4, 63, 37, 22, 77, 86, 93]
[39, 23, 32, 45, 58, 4, 37, 63, 22, 77, 86, 93]
[39, 23, 32, 45, 58, 4, 37, 22, 63, 77, 86, 93]
第3排序轮后:
[39, 23, 32, 45, 58, 4, 37, 22, 63, 77, 86, 93]
开始第4轮排序:
[39, 23, 32, 45, 4, 58, 37, 22, 63, 77, 86, 93]
[39, 23, 32, 45, 4, 37, 58, 22, 63, 77, 86, 93]
[39, 23, 32, 45, 4, 37, 22, 58, 63, 77, 86, 93]
第4排序轮后:
[39, 23, 32, 45, 4, 37, 22, 58, 63, 77, 86, 93]
开始第5轮排序:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
第5排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
开始第6轮排序:
第6排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
开始第7轮排序:
第7排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
开始第8轮排序:
第8排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
开始第9轮排序:
第9排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
开始第10轮排序:
第10排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
开始第11轮排序:
第11排序轮后:
[39, 23, 32, 45, 4, 22, 37, 58, 63, 77, 86, 93]
Java实现
public class BubbleSort {public static void bubbleSort(int [] arr) {int length = arr.length;for (int i = 0; i < length - 1; i++) {for (int j = i; j < length - 1; j++) {if (arr[j + 1] < arr[j]) {int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}}public static void main(String[] args) {int[] arr = new int[]{1, 8, 2, 5, 4, 9, 10, 6};bubbleSort(arr);for (int a :arr) {System.out.println(a);}}
}
总结
每一轮会确定一个元素的最终位置,时间复杂度为O(n^2)
ps:计划每日更新一篇博客,今天由于内容原因会分几篇文章更新,今日2023-04-23,日更第七天,昨日更新:leetcode两数、三数、四数之和