冒泡排序——重温排序（三）

内容简介：设待排序列中有先来直观地看下排序的过程，同样注意观察排序的「稳定性」。

冒泡排序——重温排序（三）大家好，欢迎来到「没人看系列」。距离这个系列的上一篇文章「希尔排序」，已经过去了3个月之久。最近开始休假，总算有点时间来补上点进度。今天来说一下「冒泡排序」。

一、算法描述

设待排序列中有 n 个记录。则排序过程一般需要经历 n-1 次冒泡。每次冒泡，会将本次待排序列中关键字最大的记录下沉，即移动到序列的末尾。移动的过程，是通过依次比较相邻记录的关键字大小，如果发生逆序，则交换。在进行第 i 趟冒泡时，对应的待排序列为 0 ... n-i-1 。

二、图示举例

先来直观地看下排序的过程，同样注意观察排序的「稳定性」。

冒泡排序——重温排序（三）

三、算法实现

「冒泡排序」的代码实现也非常简单。

void bubbleSort(int list[], int count) {
    for (int i = 0; i < count - 1; ++i) {
        for (int j = 0; j < count - i - 1; ++j) {
            if (list[j] > list[j+1]) {
                int tmp = list[j];
                list[j] = list[j+1];
                list[j+1] = tmp;
            }
        }
    }
}

注意：上面的代码，对于已经排好序的序列，也会进行 n-1 次冒泡。但其实只要上一轮冒泡没有发生记录的交换，就说明此时序列已经有序，可以直接返回。此处可以通过添加一个 flag 变量，用来记录上一轮有没有发生记录交换，没有则可以直接 return ，这样可以提高排序的效率。

四、算法分析

最好情况：若初始序列已经排好序，则只需要进行 n-1 次比较，而不需要发生交换。
最坏情况：需要执行 n-1 次冒泡，并且每次都需要进行 n-i-1 次交换。
可以看到，「冒泡排序」在序列基本有序的情况下，效率会好一些。平均来看，「冒泡排序」的时间复杂度是 O(n^2) 。

五、总结

冒泡排序的时间复杂度为 O(n^2) 。
冒泡排序是一种稳定的排序。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

计算机程序设计艺术（第1卷）

[美] Donald E. Knuth / 清华大学出版社 / 2002-9 / 80.00元

第1卷首先介绍编程的基本概念和技术，然后详细讲解信息结构方面的内容，包括信息在计算机内部的表示方法、数据元素之间的结构关系，以及有效的信息处理方法。此外，书中还描述了编程在模拟、数值方法、符号计算、软件与系统设计等方面的初级应用。此第3版增加了数十项简单但重要的算法和技术，并根据当前研究发展趋势在数学预备知识方面做了大量修改。一起来看看《计算机程序设计艺术（第1卷）》这本书的介绍吧!

码农工具