发表于: 2020-01-09 20:58:05

1 1270


今日完成

  • 概述
    • 冒泡排序是一种稳定排序,值相等的元素并不会打乱原本的顺序
    • 均时间复杂度是O(n2):每一轮都要遍历所有元素,总共遍历(元素数量-1)轮
  • 排序规则
    • 一个无序数列{5,8,6,3,9,2,1,7}:从小到大排序
    • 1 相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于或等于右侧相邻元素时,位置不变;元素9为最大的元素,“漂”到了最右侧
    • 2 第2轮排序结束后,数列右侧的有序区有了2个元素:8、9
    • 3-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倍
        • 代码外层的大循环控制着所有排序回合
        • 大循环内包含2个小循环:第1个小循环从左向右比较并交换元素,第2个小循环从右向左比较并交换元素


明日计划

评审


返回列表 返回列表
评论

    分享到