排序之冒泡排序

绝地灬酷狼 2022-10-29 01:58 202阅读 0赞

# 简介 #

在计算机科学中，排序占据着十分重要的位置，排序算法属于基础科学。常用的排序算法中包括快速排序、冒泡排序、计数排序、堆排序。我们可以通过分类来记忆这些排序算法

根据时间复杂度可以分为

*  O(n2)
    
     *  冒泡排序
     *  选择排序
     *  插入排序
     *  希尔排序
 *  O(nlog)
    
     *  快速排序
     *  归并排序
     *  堆排序
 *  O(n)
    
     *  计数排序
     *  桶排序
     *  基数排序

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1][]

> 冒泡排序的核心就是相邻元素的比较，通过n-1轮比较达到排序的结果。

冒泡算法（bubble sort），它是一种基础的**交换排序**。冒泡排序之所以叫做冒泡排序，是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点的向着数组的一侧移动。

冒泡算法的思想如下：

> 我们将相邻的元素两两比较，当一个元素大于右侧相邻元素，交换它们的位置；当一个元素小于或者等于右侧相邻元素时，位置不变。通过第一轮冒泡之后，则序列可以分为两个部分，一个是最右侧的有序区域，一个是有序去相对应的无序区。

冒泡排序是稳定排序，总共遍历n-1轮，平均时间复杂度为O(n2)。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2][]

# 代码演示 #

## 初级版本 ##

代码非常简单， 使用双循环进行排序。 外部循环控制所有的回合， 内部  
循环实现每一轮的冒泡处理， 先进行元素比较， 再进行元素交换。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 3][]

package com.atguigu.sort;
    
    import java.util.Arrays;
    
    /** * @author songquanheng * 2021/2/7-15:49 */
    public class BSort { 
        public static void main(String[] args) { 
            int[] arr = { 5, 8, 6, 3, 9, 2, 1, 7};
            bubbleSort(arr);
            System.out.println("after bubble sort");
            System.out.println(Arrays.toString(arr));
        }
    
        public static void bubbleSort(int array[]) { 
            int count = 0;
            for (int i = 0; i < array.length; i++) { 
                for (int j = 0; j < array.length - i - 1; j++) { 
                    if (array[j]>array[j+1]) { 
                        int tmp = array[j];
                        array[j ] = array[j+1];
                        array[j + 1] = tmp;
    
                        
                    }
                    count++;
                }
            }
    
            System.out.println("count = " + count);
        }
    }

程序运行之后结果如下：

count = 28
    after bubble sort
    [1, 2, 3, 5, 6, 7, 8, 9]

其中

28 = 7+6+5+4+3+2+1

**i控制趟数，i的值从0取到array.length-1趟。**

**j则控制内层循环中左边的元素的指向**。由于要访问array\[j+1\]，因此j的范围要小于**array.length-i-1**

## 数列已经有序的优化 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 4][]

因此，我们可以通过添加标志位来判断某一趟中是否发生了交换，如果没有发生交换，则说明序列已经整体有序了，就不用再进行之后的排序了。

public static void bubbleSort2(int array[]) { 
            boolean isSorted;
            for (int i = 0; i < array.length; i++) { 
                System.out.println("handle " + i + " round");
                isSorted = false;
                for (int j = 0; j < array.length - i - 1; j++) { 
                    if (array[j] > array[j + 1]) { 
                        int tmp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = tmp;
                        isSorted = true;
                    }
    
                }
                if (!isSorted) { 
                    break;
                }
            }
    
        }

利用布尔变量isSorted作为标记，如果在本轮排序中，元素有交换，则说明数列无序；如果没有数列交换，则说明数列已经有序，直接跳出大循环即可。

## 数组分为有序区和无序区 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5][]

因为右面的5、6、7、8已经是有序了，因此前4轮的比较都是无意义的。想要优化这种场景，需要确定数列的有序区。

> 我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。

public static void bubbleSort3(int array[]) { 
        boolean isSorted;
        // 记录最后一次交换的位置
        int lastExchangeIndex = 0;
        // 无序数组的边界，每次比较只要比较到这里即可。
        int sortBorder = array.length - 1;
    
        for (int i = 0; i < array.length; i++) { 
            System.out.println("handle " + i + " round");
            isSorted = false;
            for (int j = 0; j < sortBorder; j++) { 
                if (array[j] > array[j + 1]) { 
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    isSorted = true;
                    lastExchangeIndex = j;
                }
    
            }
            sortBorder = lastExchangeIndex;
            if (!isSorted) { 
                break;
            }
        }
    
    }

我们在main函数测试上述的代码：

bubbleSort3(new int[]{ 3, 4, 2, 1, 5, 6, 7, 8});
            System.out.println(Arrays.toString(arr));

输出结果如下：

handle 0 round
    handle 1 round
    handle 2 round
    handle 3 round
    [1, 2, 3, 5, 6, 7, 8, 9]

上述的结果，确实仅仅比较了4轮，还是挺厉害的。降低了比较的趟数，确实显著的增加了冒泡算法的表现。

这个过程让我想到了张磊在《**价值**》中p322页提到的精益管理。精益管理与浪费相对，如果正确识别了“浪费”，可能也就理解了精益管理99%的含义。在精益管理的范畴中，浪费是指一切消耗了资源而不创造价值的人类活动，包括需要纠正的错误，生产了无需求的产品以及由此造成的库存和积压，不必要的工序，员工的盲目走动，货物从一地到另一地的盲目搬运，由于上一道工序不及时导致下一道工序的等待，以及商品和服务不能满足消费者要求等等。

## 优化4-鸡尾酒排序 ##

> 应用场景为：大部分元素已经有序的情况。

算法真的是和应用的场景密切相关的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 6][]

这就是鸡尾酒排序的思路。 排序过程就像钟摆一样， 第1轮从左到右，  
**第2轮从右到左， 第3轮再从左到右**

代码不再附录了，感兴趣的人可直接查阅《漫画算法》P116页。

# 下载 #

[排序算法之冒泡排序][Link 1]

# 总结 #

我还记得当时我看到冒泡算法的三种优化，以及鸡尾酒排序的欣喜，学无止境是真实不虚的。我们在学习或者工作的时候，思考问题，一定要静的下来，认真的思考其中的问题和原因，深入研究，研究透澈，这样才行的。一个简单的冒泡排序其中就有这么多的弯弯绕绕，如果不是真懂真理解，模模糊糊的知道，见过，对于个人未来的发展是不利的。所以曾国藩的那句“躬身入局”还是值得我辈推崇和提倡的。

希望大家都做靠谱的人才：

*  自驱型的人。自驱型的人寻找事情背后的意义，拥有专注解决问题的最佳效率，而不需要更大的组织规模。
 *  时间敏感性的人。浪费时间就是kill people，把有限的时间使用好，是一门非常重要的功课。
 *  有同理心的人，有同理心的人往往习惯于换位思考和通盘考虑，而不是机械的完成任务。
 *  终身学习者。与具有固定性思维的人相比，拥有成长性思维的人更加重视学习和挑战，把学习作为终身的乐趣和成就，而不是短暂的功利性的斩获。

2021年2月7日16:50:11于AUX

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70]: /images/20221024/0ae662d8e13947e29003927f93998869.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1]: /images/20221024/09b51277e31543cc993efb8bf1d4bdb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2]: /images/20221024/4aa9459af5da4eada653c0d2801ed339.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 3]: /images/20221024/c8c38b5c32464a078a98f8f22ac0475d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 4]: /images/20221024/76d27177ec624615978b9b99d1ec2d1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5]: /images/20221024/35c9399ce5c34c7eb7ef7db69de8dd2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 6]: /images/20221024/14244df8bf8a42968a787a9cd5859559.png
[Link 1]: https://download.csdn.net/download/lk142500/15120479