发表于: 2020-01-09 20:58:05
1 1269
今日完成
- 概述
- 冒泡排序是一种稳定排序,值相等的元素并不会打乱原本的顺序
- 均时间复杂度是O(n2):每一轮都要遍历所有元素,总共遍历(元素数量-1)轮
- 排序规则
- 一个无序数列{5,8,6,3,9,2,1,7}:从小到大排序
- 1 相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变;元素9为最大的元素,“漂”到了最右侧
- 2 第2轮排序结束后,数列右侧的有序区有了2个元素:8、9
- 3-7 每一轮的逻辑如上
- 一个无序数列{5,8,6,3,9,2,1,7}:从小到大排序
- 鸡尾酒排序
- 存在问题
- 无序数列{2,3,4,5,6,7,8,1},元素2、3、4、5、6、7、8已经是有序的了,只有元素1的位置不对
- 冒泡排序问题:要进行7轮排序
- 流程:无序数列{2,3,4,5,6,7,8,1},第1轮从左到右,第2轮从右到左,第3轮再从左到右……
- 1 和冒泡排序一样,8和1交换
- 2 从右往左比较并进行交换
- 3 虽然实际上已经有序,但是流程并没有结束;要重新从左向右比较并进行交换——>1和2比较,位置不变;2和3比较,位置不变;3和4比较,位置不变……6和7比较——>没有元素位置进行交换,证明已经有序,排序结束
- 1 和冒泡排序一样,8和1交换
- 优缺点
- 优点:在特定条件下,减少排序的回合数
- 缺点:代码量几乎增加了1倍
- 代码外层的大循环控制着所有排序回合
- 大循环内包含2个小循环:第1个小循环从左向右比较并交换元素,第2个小循环从右向左比较并交换元素
- 存在问题
明日计划
评审
评论