排序算法_冒泡排序(scala实现)

package One {

  import scala.util.control.Breaks

  // 冒泡排序
  /*
  * 1. 什么是冒泡排序
  *       依次比较两个相邻的元素,满足条件就交换,将当前最大值或最小值交换到最后
  * 示例(正序)
  *   原数组 : 5 4 1 2 3
  *   第一次遍历 : 4 1 2 3 5
  *   第二次遍历 : 1 2 3 4 5
  *   第三次遍历 : 1 2 3 4 5
  *   第四次遍历 : 1 2 3 4 5
  * 时间复杂度
  *   初始化文件-正序时:
  *     判断次数最小=n-1
  *     交换次数最小=0
  *     时间复杂度=O(n)
  *   初始化文件-逆序时:
  *     判断次数最大=n-1 n-2 ...1 = n*(n-1)/2
  *     交换次数最小=3*n*(n-1)/2
  *     时间复杂度=O(n*n)
  * 怎样避免数组有序后,再重复判断？
  *     添加 是否交换标识 : 触发交换为true 不触发交换为false
  *     扫描后 没有数据交换则停止交换
  *
  * */
  object BubbleSort extends App {

    import scala.language.postfixOps

    // 初始化数组
    var list = Array[Int](4, 5, 3, 2, 1)
    println("排序前 : " + list.mkString(","))

    //排序
    Breaks.breakable(

      for (i <- 1 until list.length reverse) {
        var if_change = false //优化: 本次扫描是否触发 数据交换

        for (y <- 0 until i) {

          // 满足条件后,触发数据交换
          if (list(y + 1) > list(y)) {
            println(s"第${list.length - i}次扫描,第${y}次判断,交换")
            var temp = 0
            temp = list(y + 1)
            list(y + 1) = list(y)
            list(y) = temp
            if_change = true //优化: 本次扫描是否触发 数据交换
          } else {
            println(s"第${list.length - i}次扫描,第${y}次判断,不交换")
          }
        }

        // if_change = false时(没有触发交换),排序完成
        println(s"本次扫描是否触发交换 : ${if_change}")
        if (if_change == false) Breaks.break


      }
    )

    println("排序后 :" + list.mkString(","))


  }

}

// 执行结果

排序前 : 4,5,3,2,1
第1次扫描,第0次判断,交换
第1次扫描,第1次判断,不交换
第1次扫描,第2次判断,不交换
第1次扫描,第3次判断,不交换
本次扫描是否触发交换 : true
第2次扫描,第0次判断,不交换
第2次扫描,第1次判断,不交换
第2次扫描,第2次判断,不交换
本次扫描是否触发交换 : false
排序后 :5,4,3,2,1