scalaクイックソート

import scala.collection.mutable.ListBuffer

/**
  * Created by Administrator on 2016/6/25.
  *     ：         ，                   ，  ，
  *       ，              ，           right,    ，
  *      ，         ，                left right  ，  left right       。
  *          ，         ，            ，   ，             ，   。
  *                     ，        。
  *
  */
object QuickSort {
  def main(args: Array[String]) {
    var buffer = ListBuffer(49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51)
    println("sort before......")
    for(item print(item + " ")
    }
    println()
    quickSort(buffer, 0, buffer.size - 1)

    println("sort after......")
    for(item print(item + " ")
    }
  }

  def quickSort(buf: ListBuffer[Int], low: Int, high: Int): Unit = {
    if(low < high) {
      val baseline_index = getBaselineIdx(buf, low, high)
      quickSort(buf, low, baseline_index - 1)
      quickSort(buf, baseline_index + 1, high)
    }
  }
  def getBaselineIdx(buf: ListBuffer[Int], low: Int, high: Int): Int = {
    var low_ = low
    var high_ = high
    val tmp = buf(low_)

    while(low_ < high_) {
      while(low_ < high_ && buf(high_) >= tmp) {
        high_ = high_ - 1
      }
      buf(low_) = buf(high_)

      while(low_ < high_ && buf(low_) <= tmp) {
        low_ = low_ + 1
      }
      buf(high_) = buf(low_)
    }
    buf(low_) = tmp
    low_
  }
}