- 冒泡排序是一种交换排序,通过比较相邻的元素,如果反顺序则交换,直到没有反序的元素为止
冒泡排序代码
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²)
网友评论