发表于： 2020-01-09 20:58:05
1 1267
今日完成
- 概述
- 冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序
- 均时间复杂度是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个小循环从右向左比较并交换元素
- 存在问题
明日计划
评审
返回列表
评论