Java中的冒泡排序

Java中的冒泡排序

排序的第一种思想:将第一个值与后面的值相比较，如果第一个值比其他值小，那么将较大的值与第一个换位置，然后继续比较直至所有的数比较完成。这样就可以保证第一个数是最大数。然后将第二个数再重复进行一遍此操作，不同的是第二个数进行操作时不用与第一个相比，因为已经确定过第一个是最大值。

排序的第二种思想:将两个相邻的数比较(第一个值和第二个值；第二个值和第三个值；第三个值和第四个值……)，如果第一个值比第二个值小，那么将这两个值换一个位置，然后后面依次进行此操作，这样可以保证最小值在最后面。

首先冒泡排序的核心思想就是循环赋值，将两个值在条件满足的情况下交换位置。
例如:　　3 , 5　　如果第一个值小于第二个值则进行交换　　→     5 , 3
而在Java中进行换位置的操作我们不能直接交换值，直接交换值的话会将值覆盖
比如说:

package Dome;

public class Dome1 {
    
    public static void main(String[] args) {
        
        int arr[] = { 1, 2, 3, 4, 5 };
        
        System.out.println(arr[0] + ":" + arr[1]);
        
        arr[0] = arr[1]; // 将下标为1的值赋值给下标为0的值
        
        arr[1] = arr[0]; // 将下标为0的值赋值给下标为1的值
        
        System.out.println(arr[0] + ":" + arr[1]);
        
    }
    
}

但是这样交换值的方法是错误的：

因为首先进行
　　arr[0] = arr[1];
此时arr[0]已经被修改为2了也就是arr[1]的值;
再将arr[0]的值赋值给arr[1]的话他们的值就是相同的了;

所以交换值正确的做法为:

package Dome;

public class Dome1 {
    
    public static void main(String[] args) {
        
        int arr[] = { 1, 2, 3, 4, 5 };
        
        System.out.println(arr[0] + ":" + arr[1]);
        
        int temp;
        
        temp = arr[0];        //将下标为0的值赋值给temp
        
        arr[0] = arr[1]; // 将下标为1的值赋值给下标为0的值
        
        arr[1] = temp;     // 将下标为0的值赋值给下标为1的值
        
        System.out.println(arr[0] + ":" + arr[1]);
        
    }
    
}

首先定义一个与数组类型相同的变量temp(名字自定义)来储存数组中的值，先将arr[0]的赋值给temp，然后将arr[1]赋值给arr[0]，最后将temp的值赋值给arr[1]；通俗的来讲有一桶浑水和一桶干净水，如果想换个水桶装肯定不能直接将浑水往干净的水里面倒，则要另一个桶来装浑水，然后将干净的水倒入装浑水的桶里面，然后再将转移的浑水装入原来的装干净的水的水桶中，所以这里我们就需要多一个桶，也就是变量temp，这个变量的作用就是储存一个数组中的某个值，以便进行交换，避免覆盖 ；

而冒泡的核心操作就是循环进行赋值，直到排序完成；

那么我们接下来进行具体的操作(以数组[1,2,3,4,5]为例)：

1.开始我们阐述的第一种排序思想(将第一个值依次与后面的相比)：
首先进行第一个值的比较：
　　第一个值与第二个值比较满足条件进行交换　　：  2,1,3,4,5
　　第一个值与第三个值比较满足条件进行交换　　：  3,1,2,4,5
　　第一个值与第四个值比较满足条件进行交换　　：  4,1,2,3,5
　　第一个值与第五个值比较满足条件进行交换　　：  5,1,2,3,4
　　此时第一个值的比较完成，现在数组中第一个值便是数组中的最大值；

开始进行第二个值的比较：
(第二个值不需要与第一个相比因为在第一轮已经比过了)
　　第二个值与第三个值比较满足条件进行交换　　：  5,2,1,3,4
　　第二个值与第四个值比较满足条件进行交换　　：  5,3,1,2,4
　　第二个值与第五个值比较满足条件进行交换　　：  5,4,1,2,3
　　此时第二个值的比较完成，现在第二个值为数组中的第二大的值；

开始进行第三个值的比较：
　　第三个值与第四个值比较满足条件进行交换　　：  5,4,2,1,3
　　第三个值与第五个值比较满足条件进行交换　　：  5,4,3,1,2
　　此时第三个值的比较完成。

开始进行第四个值的比较：
　　第四个值与第五个值比较满足条件进行交换　　：  5,4,3,2,1
至此排序完成。

然后总结一下规律：
　　我们开始比较的值总共有四个（第一个值，第二个值，第三个值，第四个值）也就是数组的长度减1，而被比较的值是从开始比较的值的下标加1开始的然后自增，例如第一个值比较是是从第二个值开始与第一个值比较，第一轮总共比较了4次，第二轮3次，第三轮2次，第四轮1次。

然后找规律：
外层循环　内层循环开始的下标(下标是从0开始所以要减一)　内层循环次数

　　 1　　　　　　　　　　　　2-1　　　　　　　　　　　　　　　4
　　 2　　　　　　　　　　　　3-1　　　　　　　　　　　　　　　3
　　 3　　　　　　　　　　　　4-1　　　　　　　　　　　　　　　2
　　 4　　　　　　　　　　　　5-1　　　　　　　　　　　　　　　1
因为是遍历数组要使用下标，所以要从0开始所以将外层循环的1,2,3,4改为0,1,2,3

代码如下：

package Dome;

public class Dome1 {
    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5 };
        int temp; // 定义一个变量储存数组中的值
        int x = 0;// 交换的次数

        // 外层循环的次数为数组长度减1 -->arr.length - 1
        for (int i = 0; i < arr.length - 1; i++) {
            /**
             * 因为是下一个值与前面的值比较所以j的下标为i+1 而j的值会随着i增加第一次为1,第二次为2,第三次为3,第四次为4
             * 循环的次数为: 4 3 2 1 因为j自增 所以j只需要小于5即数组的长度即可
             */
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    // 进行交换
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;

                }
                x++;// 交换的次数自增+1
                
                // 查看每次操作过后的组数
                System.out.print("第" + x + "次交换" + ":	");
                for (int z = 0; z < arr.length; z++) {
                    System.out.print(arr[z] + " ");
                }
                System.out.println();
            }
        }
    }
}

运行的结果

发现每次的结果与分析时的一样。由此排序完成

1.开始我们阐述的第一种排序思想(相邻的比较)：
首先从第一个值开始比较：
　　第一个值与第二个值比较满足条件进行交换　　：  2,1,3,4,5
　　第二个值与第三个值比较满足条件进行交换　　：  2,3,1,4,5
　　第三个值与第四个值比较满足条件进行交换　　：  2,3,4,1,5
　　第四个值与第五个值比较满足条件进行交换　　：  2,3,4,5,1
　　这种操作核心原理与第一种相同，但是这种操作的结果是将最小的值往后移，第一次操作完的结果会使最后一位为最小值；
进行第二次比较：
　　第一个值与第二个值比较满足条件进行交换　　：  3,2,4,5,1
　　第二个值与第三个值比较满足条件进行交换　　：  3,4,2,5,1
　　第三个值与第四个值比较满足条件进行交换　　：  3,4,5,2,1
　　因为确定最后一个数为最小值了所以比较到倒数第二个就可以结束了，此时倒数第二个的值为倒数第二小；
进行第三次比较：
　　第一个值与第二个值比较满足条件进行交换　　：  4,3,5,2,1
　　第二个值与第三个值比较满足条件进行交换　　：  4,5,3,2,1
　　此时倒数第三个数为倒数第三小;
进行第四次比较：
　　第一个值与第二个值比较满足条件进行交换　　：  5,4,3,2,1
　　此时倒数第四个数为倒数第四小；第一个数为最大；比较完成
然后总结一下规律：
　　和第一种相似，外层循环也进行了四次，就是数组的长度减1，内层循环分别进行了4,3,2,1次；不一样的是这次的比较每次都是从第一个第一个值开始（下标对应的为0），但是循环的次数依次减少，所以我们限制循环的次数的条件要变;
找规律:
　外层循环　外层开始的下标　内层开始的下标　　内层循环次数
　　 1　　　　　　0　　　　　　　  0　　　　　　　　4
　　 2　　　　　　1　　　　　　　  0　　　　　　　　3
　　 3　　　　　　2　　　　　　　  0　　　　　　　　2
　　 4　　　　　　3　　　　　　　  0  　　　　　　     1
　　因为这次排序中外层循环的下标只用于控制外层循环的次数所以可以不用写出来；
代码如下：

package Dome;

public class Dome1 {
    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5 };
        int temp; // 定义一个变量储存数组中的值
        int x = 0;// 交换的次数

        // 外层循环的次数为数组长度减1 -->arr.length - 1
        for (int i = 0; i < arr.length - 1; i++) {
            /**
             * 因为是相邻的值比较，所以只用到了j的下标，i的下标只用来控制循环次数
             * j每自增一次就是往后面移一次相邻的两个数
             */
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] < arr[j+1]) {
                    //进行交换
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
                x++;// 交换的次数自增+1
                
                // 查看每次操作过后的组数
                System.out.print("第" + x + "次交换" + ":	");
                for (int z = 0; z < arr.length; z++) {
                    System.out.print(arr[z] + " ");
                }
                System.out.println();
            }
        }
    }
}

结果如下:

分析的与结果一致，第二种排序完成；

至此完成了两种冒泡排序，如有错误和建议请在评论留言。

　　　　　　　　　　　　　　　　 　　　　　　　　　　2019-03-25  16:27:55