冒泡排序
原理:比较两个相邻的元素,将值大的元素交换至右端
- 从第一开始比,比完一轮从第二位开始比较,所以总次数为 n-1
- 第一趟比较完成后,最后一个数字一定是最大的数字,所以不用比,以此类推,每次都可以少比较一次,第i趟比较次数 n-i
举例
int[] arr={6,3,8,2,9,1}
第1趟:
- 3,6,8,2,9,1
- 3,6,8,2,9,1
- 3,6,2,8,9,1
- 3,6,2,8,9,1
- 3,6,2,8,1,9
进行了5次比较
——————————— 第2趟: - 3,6,2,8,1,9
- 3,2,6,8,1,9
- 3,2,6,8,1,9
- 3,2,6,1,8,9 进行了4次比较 ——————————— 第3趟:
- 2,3,6,1,8,9
- 2,3,6,1,8,9
- 2,3,1,6,8,9 进行了3次比较 ——————————— 第4趟:
- 2,3,1,6,8,9
- 2,1,3,6,8,9 进行了2次比较 ———————————- 第5趟:
- 1,2,3,6,8,9 进行了1次比较
总结
由此可见n个数字需要拍n-1趟,每一趟比较n-i次,可以用双重循环语句,外层控制循环趟数,内层控制每一趟比较的次数
代码
package practice.day06;
public class BubbleSort {
public static void sort(int[] array) {
if(array==null || array.length ==0){
return;
}
int length = array.length;
//外层:需要length-1次循环比较
for(int i=0;i<length-1;i++){
//内层:每次循环需要两两比较次数,每次比较后,都会将当前最大的数放到最后的位置,所以每次比较次数递减一次
for(int j=0;j<length-1-i;j++){
if(array[j]>array[j+1]){
//交换数组array的j和j+1位置的数据
swap(array,j,j+1);
}
}
}
}
/**
* 交换数组array的i和j的位置
*/
public static void swap(int[] array,int i,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}