type
status
date
slug
summary
tags
category
icon
password
整理定义
中文名称:冒泡排序
英文名称:bubble sort
出处 | 定义 |
冒泡排序:一种典型的交换排序算法,通过交换数据元素的位置进行排序。算法重复地遍历需要排序的元素列,依次比较两个相邻的元素,如果它们的顺序(如从大到小、首字母从A到Z)为逆序就把它们交换过来。比较元素的操作重复进行,直到没有相邻元素需要交换为止。 | |
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes through the list are repeated until no swaps had to be performed during a pass, meaning that the list has become fully sorted. The algorithm, which is a comparison sort, is named for the way the larger elements "bubble" up to the top of the list.
【冒泡排序(有时称为下沉排序)是一种简单的排序算法,它逐个元素地重复遍历输入列表,将当前元素与其后面的元素进行比较,并在需要时交换它们的值。 重复对列表的这些遍历,直到在遍历期间不必执行交换,这意味着列表已完全排序。 该算法是一种比较排序,因其较大的元素“冒泡”到列表顶部的方式而得名。】 | |
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。 |
复述展开
冒泡排序 (Bubble Sort)
冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列,依次比较两个元素,如果它们的顺序错误就把它们交换过来。
遍历序列的工作是重复地进行直到没有再需要交换为止,此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。
算法步骤
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤,除了最后一个;
- 重复步骤 1~3,直到排序完成。
此处对代码做了一个小优化,加入了 is_sorted Flag,目的是将算法的最佳时间复杂度优化为 O(n),即当原输入序列就是排序好的情况下,该算法的时间复杂度就是 O(n)。
算法分析
稳定性:稳定
时间复杂度 :最佳:O(n) ,最差:O(n^2), 平均:O(n^2)
空间复杂度 :O(1)
排序方式 :In-place
冒泡算法示意图
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fdea38628-64dc-40fd-8d17-2efa87e3d554%2F875e02b5-c61a-4366-856f-700a0817104d%2F%25E5%2586%2592%25E6%25B3%25A1%25E6%258E%2592%25E5%25BA%258F_%25E8%25BD%25BB%25E5%25BA%25A6.gif?table=block&id=525f1c51-f98d-43e3-9f50-31766c438c73&t=525f1c51-f98d-43e3-9f50-31766c438c73&width=420&cache=v2)
代码展示
理解体会
1、冒泡排序作为简单排序算法,顾名思义,就是通过比较两两之间元素的大小,通过冒泡的方式将最大的沉底,所以也叫做沉底排序,然后经过N-1次冒泡,达到所有元素都排好序。
2、在写概念的过程中,发现如果使用GIF图来描述冒泡的过程会比较清晰,所以学习了如何制作GIF图。这个过程中,使用了【截图】软件来实现。有个排序的可视化网站,可以在上面设置模型的长度、排序类型就可以看到可视化的动态排序过程。
通过使用截图软件进行视频录制,然后导出成GIF图即可。
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/industry-day16
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。