冒泡排序---学习

冒泡排序

思路

依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

原始数据：

第一轮交换

本轮共进行 4 次交换，也就是 （数据的个数-1） 次

第一次交换:

由于3比6小，所以本轮没有交换。

第二次交换：

由于6比4大，所以将 6 和 4 交换位置

第三次交换:

由于6比1大，所以将 6 和 1 交换位置

第四次交换:

由于6比2大， 所以将 6 和 2 交换位置

第二轮交换

由于最后一个数已经是最大值，所以不需要比较第4个数字和第5个数字

本轮共进行 3 次交换，也就是 （数据的个数-2）

第一次交换：

由于3比4小，所以没有发生交换

第二次交换:

由于4比1大，所以互相交换位置

第三次交换:

交换4和2的位置

第三轮交换

第四，第五个数已经排好序了

本轮共进行2次交换,也就是（数据的个数-3）

第一次交换：

交换 1 和 3 的位置

第二次交换：

交换 2 和 3 的位置

第四轮交换

第3个，第4个，第5个数据已经排好序了.

本轮共进行1次交换，也就是（数据个数-1）次

第一次交换：

无需交换

交换结果

到这里原始数据已经排好序了，共进行了 4 轮交换，也就是（数据的个数-1）轮

编码

第一轮排序代码:

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {3,6,4,1,2};
        new bubbleSort().sort(value);

        System.out.println("第一次排序");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        for (int i = 0; i < value.length - 1; i++) {
            int temp;

            if (value[i] > value[i+1]){
                temp = value[i];
                value[i] = value[i+1];
                value[i+1] = temp;
            }
        }
    }
}

第二轮排序代码:

这里我们只需要把循环体中的 停止的条件变为 （value.length - 2）即可

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {3,4,1,2,6};
        new bubbleSort().sort(value);

        System.out.println("第二次排序");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        for (int i = 0; i < value.length - 2; i++) {
            int temp;

            if (value[i] > value[i+1]){
                temp = value[i];
                value[i] = value[i+1];
                value[i+1] = temp;
            }
        }
    }
}

第三轮排序代码:

这里我们只需要把循环体中的 停止的条件变为 （value.length - 3）即可

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {3,1,2,4,6};
        new bubbleSort().sort(value);

        System.out.println("第三次排序");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        for (int i = 0; i < value.length - 3; i++) {
            int temp;

            if (value[i] > value[i+1]){
                temp = value[i];
                value[i] = value[i+1];
                value[i+1] = temp;
            }
        }
    }
}

第四轮交换代码：

这里我们只需要把循环体中的 停止的条件变为 （value.length - 4）即可

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {1,2,3,4,6};
        new bubbleSort().sort(value);

        System.out.println("第四次排序");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        for (int i = 0; i < value.length - 4; i++) {
            int temp;

            if (value[i] > value[i+1]){
                temp = value[i];
                value[i] = value[i+1];
                value[i+1] = temp;
            }
        }
    }
}

到这里，我们已经发现了规律

我们只需要用一个外层循环去控制轮次即可

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {3,6,4,1,2};
        new bubbleSort().sort(value);

        System.out.println("最终结果");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        //外层循环控制进行轮次
        for (int j =1; j < value.length; j++){
            //内层循环控制交换次数
            for (int i = 0; i < value.length - j; i++) {
                int temp;
                if (value[i] > value[i+1]){
                    temp = value[i];
                    value[i] = value[i+1];
                    value[i+1] = temp;
                }
            }
            System.out.println("第" + j + "次排序");
            for (int i : value) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
    }
}

思考

如果一开始提供的数据就已经是排好序的数据，我们就不需要进行排序

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {1,2,3,4,5,6,7,8};
        new bubbleSort().sort(value);

        System.out.println("最终结果");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        for (int j =1; j < value.length; j++){
            for (int i = 0; i < value.length - j; i++) {
                int temp;
                if (value[i] > value[i+1]){
                    temp = value[i];
                    value[i] = value[i+1];
                    value[i+1] = temp;
                }
            }
            System.out.println("第" + j + "次排序");
            for (int i : value) {
                System.out.print(i + ",");
            }
            System.out.println();
        }
    }
}

我们可以加一个变量统计在一轮交换中的交换次数, 。 (提示：在每一轮结束后，不要忘记初始化count)

public class bubbleSort {
    public static void main(String[] args) {
        int[] value = {1,2,3,4,5,6,7,8};
        new bubbleSort().sort(value);

        System.out.println("最终结果");
        for (int i : value) {
            System.out.print(i + ",");
        }
    }

    public void sort(int[] value) {
        for (int j =1; j < value.length; j++){
            
            //统计
            int count = 0;
            for (int i = 0; i < value.length - j; i++) {
                int temp;
                if (value[i] > value[i+1]){
                    count = count + 1;
                    temp = value[i];
                    value[i] = value[i+1];
                    value[i+1] = temp;
                }
            }
            System.out.println("第" + j + "次排序");
            for (int i : value) {
                System.out.print(i + ",");
            }
            System.out.println();
            if (count == 0){
                return;
            }
            count = 0;
        }
    }
}

我们把数据换为

int[] value = {2,3,1,3,5,6,7,8};

这里由于第2次有交换，而第3次没有交换，所以两次交换结果一致