chapter_sorting/bubble_sort/

[giscus[bot]]

chapter_sorting/bubble_sort/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_sorting/bubble_sort/

[yunCrush]

冒泡的写法有不少，个人观点：可以想象冒泡的过程是从底部，慢慢的气泡变大直到浮出水面 。这样写是不是更合适一点呢。

public void bubbleSort(int [] nums){
        // i=0表示第一个元素，i = 1才会真正意义上的比较并排序。这样自底向上，应该更形象的比作冒泡
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<nums.length-i;j++){
            if(nums[j]>nums[j+1])
               swap(nums,j,j+1);
            }
        }
    }
public void swap(int[] nums, int i, int j) {
   if (i == j) {
      return; 
   }
 nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}

[krahets]

感谢建议！这个容我细细想一想哈

[gltianwen]

也可以下面这样，不需要额外空间：
nums[i] = nums[i] + nums[j];
nums[j] = nums[i] - nums[j];
nums[i] = nums[i] - nums[j];

[krahets]

哈喽，这种写法有两个弊端，一是速度慢，三种交换方式速度分析 ；二是当两个元素加起来 > int 取值范围时，会越界（但越界应该不影响交换）。

况且，声明一个辅助变量需要的空间微乎其微（8 bytes），本着时间比空间重要的原则，还是推荐使用中间变量。

230404 更新：#60 (reply in thread)

[gltianwen]

link中千万级交换，耗时不到1s。也不大

[what-is-me]

正常还是应该使用

 tmp = a;
 a = b;
 b = tmp;

这样的交换，因为加减和异或的交换方式只对整数运算有效，哪怕只是浮点数（特别在js中），也会出问题

[tcandzq]

大佬，请问上面的图使用ppt画的吗？

[krahets]

对的，ppt 或者 keynote

[Tttobi4s]

我觉得外层 i 可以理解成“每轮要比较的次数”，这样内层 j 就能更好理解些

[krahets]

确实！

[ghost]

我不知道在别的语言是啥样
我感觉java可以用异或来交换值 不需要开新变量
比如
a=a^b;
b=a^b;
a=a^b;
这也是很基础的保密系统
两次异或获得原文

[krahets]

可以作为一个 trick 用在面试上，实际中建议不要使用 xor 。

1. xor 交换比中间变量交换更慢。这是因为 xor 交换的三步执行必须要串行，每一步输入都依赖上一步结果；但中间变量交换的前两步是可以并行的（编译器的工作，代码层面无需关心）。
2. xor 交换通用性不好，仅适用于 int 。
3. xor 交换的代码可读性不好。

有一位高赞博主也做过测试：

• 在 MacBook 2017 上，中间变量交换比 xor 交换快 3 倍；
• 在 AMD Phenom II 上，中间变量交换比 xor 交换快 1.5 倍；

https://www.quora.com/What-is-the-algorithm-to-be-used-to-swap-two-numbers-without-using-a-temporary-variable?no_redirect=1

我非常认同一个有趣的观点：The more "normal" your code works, the better job the compiler can do. And the compiler is better at optimizing for your platform than you are.

换言之，如果 xor 真的更快更好，编译器也会帮你做替换，不需要显式地写出来。

https://stackoverflow.com/questions/16535461/why-dont-people-use-xor-swaps

[GyBernstein]

这次学习发现最后一次未交换位置的操作是待排序列中较大值和最大值碰面，基于这个优化了一点，不确定好不好

    static void bubbleSortWithFlag(int[] nums) {
        // 外循环：待排序元素数量为 n-1, n-2, ..., 1
        int index = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            boolean flag = false; // 初始化标志位
            // 内循环：冒泡操作
            for (int j = index; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 交换 nums[j] 与 nums[j + 1]
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                    flag = true; // 记录交换元素
                } else {
                    // 记录最后一个没交换的位置，在这碰到了待排元素中最大的，次大的会在此位置到i-1中
                    // 同时，若最后未进行交换，需要从头开始冒泡了
                    index = j == i - 1 ? 0 : j;
                }
            }
            if (!flag)
                break; // 此轮冒泡未交换任何元素，直接跳出
        }
    }

[GyBernstein]

这是不对的

[GyBernstein]

这样测试过了，但是太罗嗦了显得

static void bubbleSortWithFlag(int[] nums) {
    // 外循环：待排序元素数量为 n-1, n-2, ..., 1
    int index = 0;
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false; // 初始化标志位
        // 内循环：冒泡操作
        int prevIdx = index;
        for (int j = index; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                flag = true; // 记录交换元素
            } else {
                // 记录最后一个没交换的位置，在这碰到了待排元素中最大的，次大的会在此位置到i-1中
                // 同时，若最后未进行交换，需要从头开始冒泡了
                index = j == i-1 ? 0 : j;
            }
        }
        if (!flag && index == 0)
            break; // 此轮冒泡未交换任何元素，直接跳出
        if (prevIdx == index && flag) 
            index = 0; // prevIdx为待排序列最大值，这时不会有未交换的情况，手动重置index
    }
}

[zhangbx3]

您好，先不考虑算法优化增加标志的情况，我这种排序是什么算法？又像又不像冒泡排序

public static int[] bubbleSortV1(int [] disOrder){
        if(disOrder.length == 1){
            return disOrder;
        }
        for (int i = 0; i < disOrder.length; i++) {
            for(int j = i + 1 ; j < disOrder.length; j++){
                if(disOrder[i] > disOrder[j]){
                    int temp = disOrder[j];
                    disOrder[j] = disOrder[i];
                    disOrder[i] = temp;
                }
            }
        }
        return disOrder;
    }

[zhangbx3]

我想了下时间复杂度和冒泡排序也一样

[krahets]

这个相当于每轮固定指针 i ，用 j 去找最小的元素，并交换至 i 。这个运行原理本质上是选择排序，但效率并不高，因为每碰到一个更小的元素就要执行一次交换。

[zhangbx3]

感觉冒泡排序和选择排序原理都差不多，有什么大的区别吗

[krahets]

区别是一个是基于“选择”操作实现排序，一个是基于模拟“冒泡”过程实现排序。

[xiaolongma88]

想知道链式存储的冒泡排序

[krahets]

已加入任务队列

[rdou17]

冒泡排序的chunk里面是否少了一行return呢

[krahets]

哪个语言哦

[ao-wei]

冒泡排序的C语言实现中，外循环初始化条件好像有点问题吧。

[Gonglja]

是的，外层循环顺序错了，感谢指正

[murmuryu]

麻烦看下，冒泡排序C语言实现 前一版本外层循环 好像没错。如果是想对齐python的写法，修改了外层i循环条件，内层循环j 得对应修改。

[krahets]

@murmuryu 谢谢指正！已于 d9686e5 修复

[Mamong]

//冒泡排序的改进版本2
//每次记录最后交换的位置(这里是最后交换的位置之前区间[0,lastSwap)都
//是有序的)，只需要在从最后一个有序元素后一个元素继续循环交换即可
void bubbleSort2(int list[], int n){
    int lastSwap=0;
    int lastSwapTemp=0;
    //最多冒泡n-1趟
    for(int i = 0;i < n-1; i++){
        lastSwap=lastSwapTemp;
        //扩大有序区间
        for (int j = n-1; j > lastSwap; j--) {
            if (list[j-1]>list[j]) {
                swap(list[j-1],list[j]);
                lastSwapTemp = j;
            }
        }
        if (lastSwap==lastSwapTemp) {
            return;
        }
    }
}

[bnufw]

flag=False
放在循环外边也是可以的吧

[frcoo]

不可以，假设第一轮交换了，flag为true，但第二轮没有发生交换，此时应该执行break的，但flag已经是true，变不回flase了

[qw124341789]

C语言里面没有bool关键词，这是c++的

[liuliangzzz]

stdbool.h

[huiyue]

请教一下大佬，“自适应”应该怎么理解。从搜索那一章开始提到这个概念，但是一直不大理解。

[krahets]

Hi，"自适应排序"是一种排序算法的特性，指的是算法能够根据输入数据的特定属性（如已经部分排序的程度）来调整其性能。具有自适应性的排序算法在处理部分已排序的数据时，会比在处理完全随机数据时表现出更高的效率。

[HuaWang135608]

我个人认为就是充分利用输入数据的先验信息，比如二分查找就依赖有序的数据，数据有序就是一种先验信息

[xuanxuanxie]

大一的时候学数据结构的冒泡排序，学不明白；现在研一了，居然会有一种，为什么之前没看明白的感觉…………

[Tiro-Wang]

同感

[lt421]

研二，同感。

[Caplost]

选择排序如过改成每次选择个最大的，感觉就和这个类似了。

[Kai1188]

还是不一样的。如果选择排序每次选最大的，再放到队尾。这样每轮遍历都只做了一次交换。但也因为没法判断相邻两个元素的大小关系，没法进行优化。哪怕数组已经有序了，仍需要O(n^2).

[williamherry]

为啥唯独没有Ruby版代码？

[krahets]

Ruby 仍在更新

[nors1993]

感觉加了flag，也得遍历一遍元素，为什么说能优化效率呢？

[HuaWang135608]

这个标记是为了避免无效的遍历。
即某一轮不交换就表示数组已经有序，后续的遍历就不必要了。