- 冒泡排序是一种交换排序，通过比较相邻的元素，如果反顺序则交换，直到没有反序的元素为止
冒泡排序代码
int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// API 实现
Arrays.sort(arr);
// 冒泡排序
int temp;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr[j]>arr[j+1]){
temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
- 优化：添加一个 flag 来判断当前循环是否已经有序，如果有序则退出循环
boolean flag = true;
int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
// 冒泡排序
int temp;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if(arr[j]>arr[j+1]){
temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag = false;
}
}
if (!flag){
break; // 退出循环
}
}
冒泡排序性能
- 最好的情况就是排序的表本身就是有序的，那么我们只要比较次数，时间复杂度为 O(n)，最坏的情况是排序表是逆序的的，时间复杂度为 O(n²)
