首页 > 代码库 > 冒泡排序算法
冒泡排序算法
冒泡排序
简介
冒泡排序是一种简单的排序算法,属于暴力算法的一种。基本思想是通过比较相邻的元素,并将其有序化而逐步将整个序列有序化。
伪代码
procedure bubble sort(A1, A2,....,An: 整数)
for(i from 1 to n - 1)
for(j from i + 1 to n)
if(A[i] < A[j]) then 交换两个数据
C++代码(C++14)
void bubbleSort(auto array[], const int count)
{
for(int i = 0; i != count - 1; ++i)
{
for(int j = i + 1; j != count; ++j)
{
if(array[i] < array[j])
{
auto temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
}
}
缺点
- 需要对列表进行多次遍历,排序所需时间较长,不适合大量元素的排序
- 当列表已经有序依然要对整个列表多次遍历。
算法复杂度
- 由于整个列表都需要进行多次遍历比较,所以不存在最优与最坏的情况。
- 平均算法复杂度(省略掉索引的比较)
- 程序第一次遍历需要N-1次比较(第一个元素与其余元素比较),第二次需要N-2次比较(第二个元素与之后的元素比较),因此算法总共需要 N-1 + N-2 + N-3 +...+ 1 = (N^2 -N)/2 次比较,因此算法复杂度为Θ(N^2)
改进
- 对于冒泡排序而言,如果某一次遍历时未发生任何数据的交换,并且相邻的两个元素均有序,则证明列表已经有序。此时可以停止遍历。因而可以在程序中加入一个布尔变量来进行跟踪
冒泡排序算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。