排序算法之冒泡排序介绍
发布时间：2021-11-15 11:52:03 所属栏目：教程 来源：互联网
导读：冒泡排序是一种非常常见的排序算法。如同水中的一排泡泡，先冒出最大的一个泡泡。再冒出剩余泡泡中的最大泡泡，依次类推，它的排序规则如下： 从第一个元素开始，比较相邻的两个元素，如果后面的小于前面的，交换两个的位置，一直比较到最后一个 循环1中的操
|
冒泡排序是一种非常常见的排序算法。如同水中的一排泡泡，先冒出最大的一个泡泡。再冒出剩余泡泡中的最大泡泡，依次类推，它的排序规则如下： 从第一个元素开始，比较相邻的两个元素，如果后面的小于前面的，交换两个的位置，一直比较到最后一个 循环1中的操作，但已经确定的最大的元素不再参与比较 直到不确定大小顺序的元素剩余两个，然后对这两个进行比较，然后结束循环 排序图示（图片来源网络） Java实现 用java实现一个简单的冒泡排序。为了便于理解，在寻找到第一个最大元素完成后，称之为第一趟，依次类推，可以发现一共需要n-1趟 publicvoidbubbleSort() { int[] array = {6, 2, 5, 3}; for (int i = 0; i < array.length - 1; i++) {// 需要排序的趟数 for (int j = 0; j < array.length - i - 1; j++) {// 每一趟需要比较的次数 if (array[j + 1] < array[j]) { int variable = array[j + 1]; array[j + 1] = array[j]; array[j] = variable; } } System.out.println("第" + (i + 1) + "趟排序后的结果：" + Arrays.toString(array)); } System.out.println("最终的排序结果：" + Arrays.toString(array)); } console 第1趟排序后的结果：[2, 5, 3, 6] 第2趟排序后的结果：[2, 3, 5, 6] 第3趟排序后的结果：[2, 3, 5, 6] 最终的排序结果：[2, 3, 5, 6] 排序过程分析 第一趟排序 排序前：[6, 2, 5, 3] 排序后：[2, 5, 3, 6] 6与2比较，然后互换位置，然后与5比较，互换位置，最后与3比较，互换位置,此时6在最后的位置，确定最大值6，一共比较3次 第二趟排序 排序前：[2, 5, 3, 6] 排序后：[2, 3, 5, 6] 2与3比较，位置不变，然后5与3比较，然后互换位置，因为6的位置已经确定，所以5与6不再比较，一共比较2次 第三趟排序 排序前：[2, 3, 5, 6] 排序后：[2, 3, 5, 6] 2与3比较，位置不变，5,6的位置已经确定，所以不再比较，一共比较1次 由上面的分析可以看出，一共进行了1+2+...+n-1次比较。也就是n(n-1)/2次,即(N^2 - n)/2次,去除对结果影响不大的N^2 - n中的-n,以及系数0.5，得出时间复杂度为 O(N^2) (注：此处的时间复杂度自己尚未完全理解，希望明白的朋友可以给予解答) 优化 上述的排序还存在优化的空间，如果本来就是一列从小到大的数，按上述操作，很容易造成资源浪费。最理想的情况下，对于一列从小到大的数，进行n次比较，即可得出结果。如果某一趟排序中，没有出现互换操作，即表示已经得到了正确的结果，此时可以结束排序，示例如下： publicvoidbubbleSort() { int[] array = {6, 2, 5, 3}; for (int i = 0; i < array.length - 1; i++) {// 需要排序的趟数 boolean flag = false;// 默认不存在位置交换 for (int j = 0; j < array.length - i - 1; j++) {// 每一趟需要比较的次数 if (array[j + 1] < array[j]) { flag = true;// 存在位置交换，修改flag为true int variable = array[j + 1]; array[j + 1] = array[j]; array[j] = variable; } } if (!flag) { break;// 不存在位置交换 跳出循环 } } System.out.println("最终的排序结果：" + Arrays.toString(array)); }  （编辑：开发网_开封站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330459号