Scala implement Comb Sort

原创
2016/03/18 20:19
阅读数 112
/**
      *
      * @param arr 待排序的数据
      * @param o   隐式转换
      * @tparam T type
      * @return
      */
    def combSort[T](arr: Array[T])(implicit o: Ordering[T]): (Seq[T], Int) = {
      import o._
      var gap: Int = arr.length
      var hasChanged = true
      var count: Int = 0

      while (gap > 1 || hasChanged) {
        if (gap > 1) gap = (gap * 0.7).toInt

        hasChanged = false

        val consecutiveIndices = (arr.indices, arr.indices drop gap).zipped
        do {
          hasChanged = false
          consecutiveIndices foreach { (i1, i2) =>
            if (arr(i1) > arr(i2)) {
              hasChanged = true
              val tmp = arr(i1)
              arr(i1) = arr(i2)
              arr(i2) = tmp
              count += 1
              println(arr.toList)
            }
          }
        } while (hasChanged)
      }
      (arr, count)
    }



展开阅读全文
打赏
1
0 收藏
分享
打赏
0 评论
0 收藏
1
分享
返回顶部
顶部