排序算法 (I):气泡排序
最编程
2024-04-17 13:06:59
...
冒泡排序是一种通过交换元素位置实现的稳定排序方式,其特点是每一轮排序后,都会在首端或尾端产生一个已排序元素,就像水泡不断上浮一样,通过多次排序,最终所有元素变得有序。
算法过程
以递增排序为例,初始集合即为待排序集合,已排序集合初始为空
- 从待排序集合中第一个元素开始向后遍历集合中元素,比较与下一个元素值的大小,大于下一个元素值则交换两个元素位置,直到待排序集合最后一个元素;
- 标记待排序集合最后一个元素为已排序;
- 重复步骤 1,2,直到待排序集合只有一个元素
演示示例
初始状态:0 次排序
待排序集合:[6,3,4,0,2,1,8,5,9,7]
已排序集合:[]
初始状态为:
根据算法过程:
- 步骤一,从待排序集合中第一个元素开始,比较 6 和 3,比较大小并交换位置后,选择第二个元素,比较 6 和 4,比较大小并交换位置,依次遍历直到待排序集合最后一个元素;
- 步骤二,标记待排序集合中的最后一个元素为已排序,即元素 9 标记为已排序,从待排序集合中移除该元素
1 次排序后
待排序集合:[3, 4, 0, 2, 1, 6, 5, 8, 7]
已排序集合:[9]
根据算法过程步骤三,待排序集合中不止一个元素,所以重复执行步骤一、二:
- 步骤一,遍历待排序集合,选择第一个元素,比较 3,4,比较大小后,选择第二个元素,比较 4,0,比较大小并交换位置,选择第三个元素,比较4,2,依次遍历直到集合最后一个元素;
- 步骤二,标记最后一个元素为已排序
2 次排序后
待排序集合:[3, 0, 2, 1, 4, 5, 6, 7]
已排序集合:[8, 9]
...
...
...
9 次排序后
待排序集合:[0]
已排序集合:[1, 2, 3, 4, 5, 6, 7, 8, 9]
观察以上过程可知,每次排序后会有一个元素变为已排序,即有一个元素处于正确的位置上。所以 个元素的序列,经过 次排序后,则有 个元素处于已排序状态,则剩下的一个元素不再需要进行排序。
算法示例
def bubbleSort(arr):
for i in range(1, len(arr)): # 迭代次数
flag = True
for j in range(len(arr) - i): # 遍历比较每个元素与下一个元素值大小
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
flag = False
if flag:
break
代码分析 :
- 以上代码中,第一层循环为需要进行的迭代次数,元素个数为 的集合,最多需要 次迭代即可确定 个元素的位置,即完成排序;
- 第二层循环为待排序集合中元素的遍历比较大小操作,随着迭代次数的增加,待排序元素个数减少;
- 代码中增加了一个 flag 标志变量,用于标志排序结束状态。若某一轮迭代中,待排序集合中元素遍历过程中,没有发生元素位置交换操作,则该待排序集合为有序的,排序算法结束。
算法分析
冒泡排序是一种稳定排序算法,排序过程中,如果两个元素值相等,则不交换元素位置。对于 个元素的序列:
- 最坏情况下,当序列为逆序时,需要 次迭代才能结束排序过程, 每一次遍历都比较并交换待排序集合中所有元素位置,即第 次迭代,遍历的元素个数为 ,所以最坏情况下,算法的交换复杂度和比较复杂度都为 ;
- 最好情况下,当序列为已排序时,第一次迭代即可结束排序过程,第一次遍历元素个数为 次,交换次数为 0,所以最好情况下,算法的比较复杂度为 ,交换复杂度为 0。
算法执行过程中,不需要申请额外的序列空间来保存临时元素,属于原地排序方式,所以算法的空间复杂度为 。
github
链接:冒泡排序
上一篇: # 冒泡排序算法的原理和实现
推荐阅读
-
[广度优先搜索] [拓扑排序] [C++ 算法] 913.猫和老鼠
-
以史为鉴:排序算法的新见解
-
Redux 排序与分析 [I: 减速器与调度]。
-
js 算法 - 插入排序(折叠半插入排序)
-
图解快速排序算法--双端检测法
-
正负偏差变量 即 d2+、d2- 分别表示决策值中超出和未达到目标值的部分。而 di+、di- 均大于 0 刚性约束和目标约束(柔性目标约束有偏差) 在多目标规划中,>=/<= 在刚性约束中保持不变。当需要将约束条件转换为柔性约束条件时,需要将 >=/<= 更改为 =(因为已经有 d2+、d2- 用来表示正负偏差),并附加上 (+dii-di+) 注意这里是 +di、-di+!之所以是 +di,-di+,是因为需要将目标还原为最接近的原始刚性约束条件 优先级因素和权重因素 对多个目标进行优先排序和优先排序 目标规划的目标函数 是所有偏差变量的加权和。值得注意的是,这个加权和都取最小值。而 di+ 和 dii- 并不一定要出现在每个不同的需求层次中。具体分析需要具体问题具体分析 下面是一个例子: 题目中说设备 B 既要求充分利用,又要求尽可能不加班,那么列出的时间计量表达式即为:min z = P3 (d3- + d3 +) 使用 + 而不是 -d3 + 的原因是:正负偏差不可能同时存在,必须有 di+di=0 (因为判定值不可能同时大于目标值和小于目标值),而前面是 min,所以只要取 + 并让 di+ 和 dii- 都为正值即可。因此,得出以下规则: 最后,给出示例和相应的解法: 问题:某企业生产 A 和 B 两种产品,需要使用 A、B、C 三种设备。下表显示了与工时和设备使用限制有关的产品利润率。问该企业应如何组织生产以实现下列目标? (1) 力争利润目标不低于 1 500 美元; (2) 考虑到市场需求,A、B 两种产品的生产比例应尽量保持在 1:2; (3)设备 A 是贵重设备,严禁超时使用; (4)设备 C 可以适当加班,但要控制;设备 B 要求充分利用,但尽量不加班。 从重要性来看,设备 B 的重要性是设备 C 的三倍。 建立相应的目标规划模型并求解。 解:设企业生产 A、B 两种产品的件数分别为 x1、x2,并建立相应的目标计划模型: 以下为顺序求解法,利用 LINGO 求解: 1 级目标: 模型。 设置。 variable/1..2/:x;! s_con_num/1...4/:g,dplus,dminus;!所需软约束数量(g=dplus=dminus 数量)及相关参数; s_con(s_con_num);! s_con(s_con_num,variable):c;!软约束系数; 结束集 数据。 g=1500 0 16 15. c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(1);!第一个目标函数;!对应于 min=z 的第一小部分;! 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); !使用设置完成的数据构建软约束表达式; ! !软约束表达式 @for(variable:@gin(x)); !将变量约束为整数; ! 结束 此时,第一级目标的最优值为 0,第一级偏差为 0: 第二级目标: !求 dminus(1)=0,然后求解第二级目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(2)+dplus(2);!第二个目标函数 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标结果 @for(variable:@gin(x)); ! 结束 此时,第二个目标的最优值为 0,偏差为 0: 第三目标 !求 dminus(2)=0,然后求解第三个目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=3*dminus(3)+3*dplus(3)+dminus(4);!第三个目标函数。 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标约束条件; ! dminus(2)+dplus(2)=0; !第二个目标约束条件 @for(variable:@gin(x));! 结束 最终结果为 x1=2,x2=4,dplus(1)=100,最优利润为
-
6: 算法基础 - 6.3: 排序算法,6.4:算法策略
-
学习部分排序、插入排序、气泡排序和希尔排序。
-
探索 Java 世界中的七种排序算法(上) - 希尔排序(收缩递增排序)
-
简单而经典:Java 冒泡排序算法详解