共计 1381 个字符,预计需要花费 4 分钟才能阅读完成。
冒泡排序简介
冒泡排序(Bubble Sort),是一种计算机科学畛域的较简略的排序算法。
它反复地走访过要排序的元素列,顺次比拟两个相邻的元素,如果程序(如从大到小、首字母从 Z 到 A)谬误就把他们替换过去。走访元素的工作是反复地进行直到没有相邻元素须要替换,也就是说该元素列曾经排序实现。
这个算法的名字由来是因为越小的元素会经由替换缓缓“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
算法原理
将邻近的两个数字两两进行比拟,依照从小到大或者从大到小的程序进行替换。
算法原理示意图
数组冒泡排序前↓↓↓
冒泡排序执行过程 [gif 动图]↓↓↓
数组冒泡排序后↓↓↓
代码实现
public class Sort {public static void main(String[] args) {int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
bubbleSort(arr);
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
System.out.println(Arrays.toString(arr));
}
/**
* 冒泡排序
* @param arr 想要排序的数组
*/
public static void bubbleSort(int[] arr){
// 管制比拟轮数
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 为一个长期变量,为了存储替换时的长期值
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
这里须要思考几个问题
- 外层的循环起到什么作用 / 外层循环代表什么?
- 外层循环中的 -1 是做什么的?
- 内层的循环起到什么作用 / 内层循环代表什么?
- 内层循环中的 -1 是做什么的?
- 内层循环中的 -i 是做什么的?
- 长期变量 temp 起到什么作用?
首先须要了解的是冒泡排序是从头开始,两两比拟,将最大的数放到开端。而后再次从头开始,以此类推……。
-
外层的循环起到什么作用 / 外层循环代表什么?
总共循环了多少轮, 或者能够了解为将最大值放在开端的次数
-
外层循环中的 -1 是做什么的?
因为咱们每次都是从头开始比拟, 并且每次都会将最大的数顺次放在开端, 当只剩最初一个数时, 它曾经是咱们的最小的数了, 而且就在第一位, 咱们再将它与其它的数进行比拟就曾经没有意义了, 所以咱们用到了 -1
-
内层的循环起到什么作用?
每轮比拟多少次, 或者能够了解为两两替换的次数
-
内层循环中的 -1 是做什么的?
因为咱们是两两进行比拟,arr[j] > arr[j+1],咱们在做每轮比拟的最初时,咱们只须要比拟倒数第二位和倒数第一位即可,因为咱们 arr[n] 中的 n 示意的是咱们数组的下标,不 -1 会呈现数组下标越界异样 arr.length – 1
-
内层循环中的 -i 是做什么的?
i 是咱们外层循环的变量,能够了解为将最大值放在开端的次数,或者开端曾经排序好了几个值,所以为了晋升效率不去做过多运算,咱们将内层循环的次数改为 arr.length – i
-
长期变量 temp 起到什么作用?
长期变量是为了存储替换过程中的长期值,使之在替换过程中值能够不被笼罩掉,得到原来的值