算法精讲:冒泡排序

1.基本思想

n个人站队为例,从第一个人开始,依次比较相邻的两个人是否逆序对,(高的在前,矮的在后),若逆序便交换两人,也就是第一个人与第二个人相比较,若逆序便交换两人,第二个人和第三个人比较,若逆序便交换两人,……,直到第n-1个人与第n个人比较为止。经过一轮比较后,最高的那个人到了最后。

接着,原来n个人的排序问题,就转变成了n-1个人的排序,第二轮排序与第一轮很相似,只不过排序直到直到第n-2个人与第n-1个人比较为止。

这样进行n-1轮排序后,原来的序列就会变成有序的序列。

时间复杂度:O(

冒泡排序还有一个简单的优化。

对于某些数据,我们发现,并不需要n-1轮才能排完。于是,我们可以定义一个布尔变量,判断是否有交换,如果没有交换,说明排序已经完成,进而减少几趟排序。

排序过程

初始序列:4 2 5 6 3 1

第一趟排序:

4 2 5 6 3 1

4和2交换

2 4 5 6 3 1

2 4 5 6 3 1

2 4 5 6 3 1

6和3交换

2 4 5 3

相关推荐

  1. 算法冒泡排序

    2024-05-09 15:26:03       13 阅读
  2. 算法:选择排序

    2024-05-09 15:26:03       11 阅读
  3. 排序算法——冒泡排序

    2024-05-09 15:26:03       42 阅读
  4. 排序算法冒泡排序

    2024-05-09 15:26:03       25 阅读
  5. 排序算法-冒泡排序

    2024-05-09 15:26:03       15 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-05-09 15:26:03       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-05-09 15:26:03       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-05-09 15:26:03       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-05-09 15:26:03       20 阅读

热门阅读

  1. C++类型与声明

    2024-05-09 15:26:03       14 阅读
  2. 每天一个数据分析题(三百一十三)-漏斗模型

    2024-05-09 15:26:03       16 阅读
  3. var, let, const 的区别

    2024-05-09 15:26:03       12 阅读
  4. poker(typescript版)

    2024-05-09 15:26:03       13 阅读
  5. (六)Linux的Shell编程(下)

    2024-05-09 15:26:03       11 阅读
  6. 点击菜单改变svg图标颜色

    2024-05-09 15:26:03       11 阅读
  7. GUIDELINES FOR THE PREPARATION OF FINAL YEAR PROJECT REPORT

    2024-05-09 15:26:03       10 阅读
  8. 头歌python本月天数

    2024-05-09 15:26:03       8 阅读