黑马程序员技术交流社区

标题: 萌新排序之冒泡 [打印本页]

---

作者: PaulY    时间: 2019-1-15 23:12
标题: 萌新排序之冒泡

冒泡排序

基本思想：
        每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换
优点：
        每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。
前提：顺序存储结构

具体实现过程：
       相较于快排，归并类排序等来说的话，冒泡排序理解难度很低，通过for循环嵌套可以很容易的实现，内层循环负责完成每一次排序内容的互换调整，通过数组下标index累加完成遍历，通过temp作暂时存储完成与对应元素和index+1的对应元素大小的互换，循环时注意数组边界，外层循环负责整个排序算法的次数，在循环结束时完成排序算法。

还是用上次的数组{ 56, 92, 24, 37, 48, 86, 13, 39, 50, 90} 共10个元素。

基本步骤：
       定义temp作为数据交换的媒介，mark做标记保存数组是否发生交换，index跟index+1则对应当前元素下标和后继元素下标，index存放数值较小的元素，index+1存放数值较大的元素。

整组元素出态如上图，蓝色箭头表示遍历方向，

index = 0时，对应数组元素数值56，index + 1 对应数组元素数值92，56 < 92，无需发生交换，循环+1

index = 1，对应数组元素数值92，index + 1 对应数组元素数值24，24 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1

index = 2，对应数组元素数值92，index + 1 对应数组元素数值37，37 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1

index = 3，对应数组元素数值48，index + 1 对应数组元素数值92，48 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1

index = 4，对应数组元素数值86，index + 1 对应数组元素数值92，86 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1

index = 5，对应数组元素数值13，index + 1 对应数组元素数值92，13 < 92，满足交换条件，通过temp交换二者数据，然后循环继续+1

后续几个元素交换过程同上。



最后最大值92换至数组尾端，此时，一趟排序完成。


下图为整个排序的输出情况：




代码如下：

[Java] 纯文本查看 复制代码

public BubbleSort(int[] array){

        System.out.println("=====================冒泡排序=====================");

        int temp = 0;

        int mark = 1, arrayLenghtcount = array.length, count = 1;

        for (int index = 0; index < array.length - 1; index++) {

            if(mark == 0 || arrayLenghtcount == 1){

                break;

            }

            mark = 0;              //标记位置，置0时未发生交换，置1则发生交换

            for (int index2 = 1; index2 < arrayLenghtcount; index2++) {

                if(array[index2 - 1] > array[index2]){

                    mark = 1;

                    temp = array[index2 - 1];

                    array[index2 - 1] = array[index2];

                    array[index2] = temp;

                }

            }

            System.out.println();

            System.out.print("第" + count + "次冒泡排序结果：");

            for (int outNumber = 0; outNumber < array.length; outNumber++) {

                System.out.print(array[outNumber] + " ");

            }

            count++;

            System.out.println();

            arrayLenghtcount--;    //每次排序会确定一位关键字，此排序采取增序完成排列，每次-1减少循环次数

        }

    }

算法优化部分：

由于每次必定会确定当前排序元素中的最大值（或者最小值），所以每次循环时，可以加一句循环自减功能来达到减少遍历的长度，同时，在内循环的交换语句内可以设置标记mark，用来保存每次遍历是否发生交换，如果任意一次没有发生任何交换，则整个数组此时已趋于有序，可直接跳出循环。

时间复杂度：

平均时间复杂度为O(n2)。                  

空间复杂度：
由于在交换过程中只需要一个缓冲元素temp，所以为1。
稳定性：
算法稳定。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2