冒泡排序(Bubble Sort)
冒泡排序是简单经典的排序算法,它重复地走访过要排序的元素,依次比较相邻两个元素,如果他们的顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序算法的运作如下:
- 比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
冒泡排序的优点:
每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,没进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。
代码:
public class BubbleSort {
public static void main(String[] args) {
int[] arr1 = {20, 5, 14, 9, 8, 7, 24, 7, 10};
sort(arr1);
System.out.println(Arrays.toString(arr1));
}
private static void sort(int[] arr1) {
for (int i = 0; i < arr1.length - 1; i++) { //外层循环控制排序趟数
for (int j = 0; j < arr1.length - 1-i; j++) { //内层循环控制每一趟排序多少次
if (arr1[j] < arr1[j + 1]) {
int a;
a = arr1[j];
arr1[j] = arr1[j + 1];
arr1[j + 1] = a;
}
}
}
}
}
输出结果: