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

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

冒泡排序——重温排序（三）大家好，欢迎来到「没人看系列」。距离这个系列的上一篇文章「希尔排序」，已经过去了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) 。
冒泡排序是一种稳定的排序。

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

查看所有标签

猜你喜欢:

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

码农书籍

Cyberwar

Kathleen Hall Jamieson / Oxford University Press / 2018-10-3 / USD 16.96

The question of how Donald Trump won the 2016 election looms over his presidency. In particular, were the 78,000 voters who gave him an Electoral College victory affected by the Russian trolls and hac......一起来看看《Cyberwar》这本书的介绍吧!

码农工具