美文网首页
冒泡排序——重温排序(三)

冒泡排序——重温排序(三)

作者: 雷曼同学 | 来源:发表于2018-06-16 13:04 被阅读30次

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

    获取更佳的阅读体验,请访问原文地址 【Lyman's Blog】冒泡排序——重温排序(三)

    相关文章

      网友评论

          本文标题:冒泡排序——重温排序(三)

          本文链接:https://www.haomeiwen.com/subject/picbeftx.html