【数据结构与算法之排序与查找】冒泡排序

喜欢ヅ旅行 2024-03-25 16:38 110阅读 0赞

#### 【数据结构与算法之排序与查找】冒泡排序 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之排序与查找】冒泡排序

冒泡排序又叫起泡排序，利用“交换”性质，

基本思想：

首先将待排序序列中的第1个元素array\[0\]与第2个元素array\[1\]比较，若前者大于后者，则两者交换，否则不动。

然后将第2个元素array\[1\]与第3个元素array\[2\] 比较，若前者大于后者，则两者交换，否则不动。

重复操作，直到将n - 1个元素与第n 个元素比较完毕。这样就完成了冒泡的第一趟。第一趟完成后，整个序列中的最大元素会被交换到整个序列的尾部，也就是第n个位置上array\[n - 1\]。

然后进行第2趟 冒泡，即对序列中的array\[0\] ~ array\[n - 2\] 这些元素再进行冒泡操作，这样序列中第2大的元素回来到序列的array\[n - 2\] 位置上。

…

以此类推，当执行完n - 1趟冒泡后，就可以将序列中最后两个元素中较大的元素交换到序列的第2个位置上 array\[1\] ，第1个位置上array\[0\] 上的元素就是整个序列中最小的元素。

举个栗子：

![在这里插入图片描述][9142ff402a6d479a9d8efba2bdc8027a.png_pic_center]

其实可以看到，冒泡排序过程中，如果某趟并没有发生元素交换，说明当前序列已经有序了，不需要再进行下一趟排序，过程即可结束掉。

所以可以在传统冒泡上做一个FLAG 用于标记本趟排序是否有元素交换行为发生。

*  flag = 1，表示本趟排序过程中仍有元素发生交换
 *  flag = 0，表示本趟排序过程中已经没有交换行为发生

Java实现代码：

public static void BublleSort(int[] array) {
        
        int flag = 1;
    
        for (int i = 0; i < array.length - 1 && flag == 1; i++) {
        
            flag = 0; // 初始化为0
    
            for (int j = 0; j < array.length - i - 1; j++) {
        
                if (array[j] > array[j + 1]) {
        
                    // 交换
                    int tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
    
                    flag = 1; // 发生数据交换，将flag 置为1
                }
            }
        }
    }

测试

public static void main(String[] args) {
        
    
        int[] array = {
        3, 12, 20, 1, 0, 5, 8, 19, 5};
        BublleSort(array);
    
        for (int e : array) {
        
            System.out.print(e + " ");
        }
    
    }

运行结果

![在这里插入图片描述][7e5976341e9c46bea938b7bca3eab8a0.png_pic_center]

[9142ff402a6d479a9d8efba2bdc8027a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/582e52c5b48142b9a9559f5d367353e3.png
[7e5976341e9c46bea938b7bca3eab8a0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ccc96d99fd464767a57530f9800b7cec.png