算法-冒泡排序

基本思路一：

    将一个数组中总数为N且不重复并乱序的正整数 转换成 正序的正整数数组。分别为：1,2,3,4,...,N第一次[index=0]循环：第一位数与其他数[N-1位数]相比第二次[index=1]循环：第二位数与其他数[N-2位数]相比.           ..           ..           .第N次[index=N-1]循环：第N位数与其他数[0位数]相比分析：从上面来看,每一次的循环,里层都有多次遍历比较！归纳来看：随机看某一次的循环进行提炼有：伪代码：for (外层i次循环) {for (里层i-1次循环) {// 若前面的数 > 后面的数,则发生交换if (前面的数 > 后面的数) {swap(前面的数,后面的数);}}}

代码如下：Java编写

import java.util.Arrays;public class BubbleSort {private static void bubbleSort(int[] nums) {for (int i = 0, n = nums.length; i < n - 1 ; ++i) {for (int j = 0; j < n - i - 1; ++j) {if (nums[j] > nums[j + 1]) {swap(nums, j, j + 1);}}}}private static void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}public static void main(String[] args) {int[] nums = {100,50,90,70,66,10,32,48,99,45,69,2, 7, 9, 5, 8};bubbleSort(nums);System.out.println("执行结果：" + Arrays.toString(nums));}
}

执行结果

执行结果：[2, 5, 7, 8, 9, 10, 32, 45, 48, 50, 66, 69, 70, 90, 99, 100]

基本思路二：

将一个数组中总数为N且不重复并乱序的正整数 转换成 正序的正整数数组。
分别为：1,2,3,4,...,N

第一次[index=0]循环：第一位数与其他数[N-1位数]相比
第二次[index=1]循环：第二位数与其他数[N-2位数]相比.           ..           ..           .
第N次[index=N-1]循环：第N位数与其他数[0位数]相比

分析：
从上面来看,每一次的循环,里层都有多次遍历比较！并且定义一个布尔变量 hasChange，用来标记每轮是否进行了交换。在每轮遍历开始时，将 hasChange 设置为 false。若当轮没有发生交换，说明此时数组已经按照升序排列，hasChange 依然是为 false。此时外层循环直接退出，排序结束。

归纳来看：随机看某一次的循环进行提炼有：

伪代码：for (外层i次循环) {boolean hasChange = true;for (里层i-1次循环) {hasChange = false;// 若前面的数 > 后面的数,则发生交换if (前面的数 > 后面的数) {swap(前面的数,后面的数);hasChange = true;}}}

代码如下：Java编写

import java.util.Arrays;public class BubbleSort {private static void bubbleSort(int[] nums) {boolean hasChange = true;for (int i = 0, n = nums.length; i < n - 1 && hasChange; ++i) {hasChange = false;for (int j = 0; j < n - i - 1; ++j) {if (nums[j] > nums[j + 1]) {swap(nums, j, j + 1);hasChange = true;}}}}private static void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}public static void main(String[] args) {int[] nums = {100,50,90,70,66,10,32,48,99,45,69,2, 7, 9, 5, 8};bubbleSort(nums);System.out.println("执行结果：" + Arrays.toString(nums));}
}

执行结果

执行结果：[2, 5, 7, 8, 9, 10, 32, 45, 48, 50, 66, 69, 70, 90, 99, 100]

两种思路的区别

当数组中的数组特别多的情况下,在执行的效率上 思路二 要比 思路一 更高效,在数值不太多的情况下,这种效果是不太明显的！

总结

在整理过程中可能会在以下这些地方犯错或理解模糊，要着重注意。

1. 在外层循环中，对于初始值的理解不是很到位，对于开发来讲，一定要养成数字开始要从0开始计数，N-1下标结尾的惯性思维。

2. 在里层循环中，[首先理解什么是冒泡排序？有生活经验的都知道，烧开水是的气泡是从底部网上冒泡。我想这大概是名字的由来吧！哈哈哈！]，所以初始值一定是 int j=0，条件中j < n - i - 1，其实就是 j < (n - 1) - i。每一次遍历后最大的数是放在最后的，自然形成顺序是从后往前的。

3. 本质上，在for循环中的第③个条件中【for(①，②，③){...}】，i++ 和 ++i 没什么区别。

4. 交换(swap)数值时注意，不要赋值出错。举个生活中的例子，现在有两个瓶子，一个装的酱油，一个装的是醋。现在想要将二者互换，此时需要一个空容器（比如是空瓶子）来做临时过渡，第一步：将酱油先倒入空瓶子x，酱油瓶y就会变成空的；第二步：将醋倒入酱油瓶y中，醋瓶z就会变成空的；第三步：将空瓶x中的酱油倒入醋瓶z中；就完成了两者的交换啦。