数据结构与算法——冒泡排序

Yang_River 发布于2019-08-16 15:51 / 876人阅读

摘要：多练练排序算法，不仅能够让我们知道一些排序方法的底层实现细节，更能够锻炼我们的思维，提升编程能力。排序算法的稳定性一个稳定的排序，指的是在排序之后，相同元素的前后顺序不会被改变，反之就称为不稳定。

1. 导言

因为这是排序算法系列的第一篇文章，所以多啰嗦几句。

排序是很常见的算法之一，现在很多编程语言都集成了一些排序算法，比如Java 的Arrays.sort()方法，这种方式让我们可以不在乎内部实现细节而直接调用，在实际的软件开发当中也会经常使用到。但是站在开发者的角度而言，知其然必须知其所以然。多练练排序算法，不仅能够让我们知道一些排序方法的底层实现细节，更能够锻炼我们的思维，提升编程能力。现在很多技术面试也会涉及到基本的排序算法，所以多练习是有好处的。

文中涉及到的代码都是Java实现的，但是不会涉及到太多的Java语言特性，并且我会加上详细的注释，帮助你理解代码并且转换成你熟悉的编程语言。

常见的排序算法有以下10种：

冒泡排序、选择排序、插入排序，平均时间复杂度都是O(n²)

希尔排序、归并排序、快速排序、堆排序，平均时间复杂度都是O(nlogn)

计数排序、基数排序、桶排序，平均时间复杂度都是O(n + k)

在开始具体的排序算法讲解之前，先得明白两个概念：

原地排序：指的是在排序的过程当中不会占用额外的存储空间，空间复杂度为O(1)。

排序算法的稳定性：一个稳定的排序，指的是在排序之后，相同元素的前后顺序不会被改变，反之就称为不稳定。举个例子：一个数组 [3，5，1，4，9，6，6，12] 有两个6（为了区分，我把其中一个 6 加粗），如果排序之后是这样的：[1，3，4，5，6，6，9，12]（加粗的 6 仍然在前面），就说明这是一个稳定的排序算法。

2. 言归正传

冒泡排序的思路其实很简单，一个数据跟它相邻的数据进行大小的比较，如果满足大小关系，就将这两个数据交换位置。一直重复这个操作，就能将数据排序。

举个例子，假如有数组 a[3,5,1,4,9,6]，第一次冒泡的操作如下图所示：

重复进行这个操作，6次冒泡之后，数据排序完成。

根据这个思路，应该能很容易能够写出下面的代码实现冒泡排序：

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n <= 1) return;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

但是这个排序算法还可以进行优化，当冒泡操作已经没有数据交换的时候，说明排序已经完成，就不用在进行冒泡操作了。例如上面的例子，第一次冒泡之后，数据为 [3,1,4,5,6,9]，再进行一次冒泡，数据变为 [1,3,4,5,6,9]，此时已经完成了排序，就可以结束循环了。

所以针对这个数组的排序，上面的代码需要6次冒泡才能完成，其中有4次都是不需要的。所以可以对代码进行优化：

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n <= 1) return;
        for (int i = 0; i < n; i++) {
            boolean flag = false;//判断是否有数据交换

            for (int j = 0; j < n - i - 1; j++) {
                //如果data[j] > data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

好了，冒泡排序的基本思路和代码都已经实现，最后总结一下：

冒泡排序是基于数据比较的

最好情况时间复杂度是O(n)，最坏情况时间复杂度是O(n²)，平均时间复杂度是O(n²)

冒泡排序是原地排序算法，并且是稳定的。

云服务器 GPU云服务器冒泡排序前端冒泡排序冒泡排序代码 js冒泡排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73741.html

JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
数据结构与算法（二）：带你读懂冒泡排序（Bubble Sorting）

摘要：经过一次冒泡排序，最终在无序表中找到一个最大值，第一次冒泡结束。也是我们后面要说的冒泡排序的优化。冒泡排序只执行第一层循环，而不会执行第二层循环。因此冒泡排序的时间复杂度是。 showImg(https://user-gold-cdn.xitu.io/2019/6/19/16b6f986df6880f9?w=640&h=142&f=gif&s=17175);showImg(https:...

chuyao 2019-08-19 11:46 评论0 收藏0
Java 数据结构与算法系列之冒泡排序

摘要：冒泡排序一种运行效率很低的排序算法，然而虽然排序效率低，确实排序入门很重的算法，因为冒泡排序的思路是最简单最容易理解的排序算法了。二冒泡排序定义冒泡排序是一种通过两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止的交换排序。一、前言相信大部分同学都已经学过数据结构与算法这门课了，并且我们可能都会发现一个现象就是我们所学过的数据结构与算法类的书籍基本都是使用 C 语言来...

1treeS 2019-08-15 17:40 评论0 收藏0
你知道和你不知道的冒泡排序

摘要：用来标示该轮冒泡排序中，数组是否是有序的。适用情况当冒泡算法运行到后半段的时候，如果此时数组已经有序了，需要提前结束冒泡排序。当第一轮冒泡排序结束后，元素会被移动到下标的位置。这篇文章包含了你一定知道的，和你不一定知道的冒泡排序。 gif看不了可以点击【原文】查看gif。源码: 【地址】 1. 什么是冒泡排序可能对于大多数的人来说比如我，接触的第一个算法就是冒泡排序。我看过的很...

Worktile 2019-08-16 18:23 评论0 收藏0
Github标星2w+，热榜第一，如何用Python实现所有算法

摘要：归并排序归并排序，或，是创建在归并操作上的一种有效的排序算法，效率为大符号。以此类推，直到所有元素均排序完毕。与快速排序一样都由托尼霍尔提出的，因而也被称为霍尔选择算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);编译：周素云、蒋宝尚学会了Python基础知识，想进阶一下，那就来点算法吧！毕竟编程语言只...

zxhaaa 2019-07-31 10:23 评论0 收藏0