内容简介:设待排序列中有先来直观地看下排序的过程,同样注意观察排序的「稳定性」。
大家好,欢迎来到「没人看系列」。距离这个系列的上一篇文章「希尔排序」,已经过去了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.冒泡排序
- 排序算法之冒泡排序改进算法
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序
- 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Functional Programming in Scala
Paul Chiusano、Rúnar Bjarnason / Softbound print / 2014-9-14 / USD 44.99
Functional programming (FP) is a programming style emphasizing functions that return consistent and predictable results regardless of a program's state. As a result, functional code is easier to test ......一起来看看 《Functional Programming in Scala》 这本书的介绍吧!