Groovy Scala functional programming 实现冒泡排序算法

 

 

 

 

今日蛋疼应某人要求用functional programming实现冒泡排序，找了段erlang代码转换成了groovy

 

 

def bubbleSortP(List list) {
    if (list?.size() == 1)
        list
    else {
        def rest = []
        if (list.size() > 2)
            rest = list[2..list.size() - 1]
        if (list.get(0) > list.get(1)) {

            [list.get(1)] + bubbleSortP([list[0]] + rest)
        } else {
            [list.get(0)] + bubbleSortP([list[1]] + rest)
        }
    }

}

def bubbleSort(List list) {
    if (list?.size() == 1)
        list
    else {
        List sublist = bubbleSortP(list)
        bubbleSort(sublist[0..sublist.size() - 2]) + sublist[sublist.size() - 1]
    }

}



def tobeSort = [6, 5, 3, 1, 8, 7, 2, 4]

println bubbleSort(tobeSort)

下面是使用了inject (left fold) 的代码

def bubbleSort(List list) {
    if (list?.size() == 1)
        list
    else {
        List sublist = list.inject([]) {List previousResult, iterationValue ->
            if(previousResult.size() == 0)
                previousResult << iterationValue
            else{
                final def last = previousResult[previousResult.size() - 1]
                if(iterationValue > last)
                    previousResult + [iterationValue]
                else{
                    previousResult << last
                    previousResult.set(previousResult.size() - 2, iterationValue)
                    previousResult
                }
            }

        }
        bubbleSort(sublist[0..sublist.size() - 2]) + sublist[sublist.size() - 1]
    }

}



def tobeSort = [6, 5, 3, 1, 8, 7, 2, 4]

println bubbleSort(tobeSort)

 

最后是scala版本

 

 

object BubbleSort {


  def bubbleSort(list: List[Int]): List[Int] = {
    if (list.size == 1)
      list;
    else {
      val subList = list.foldLeft(List[Int]())((previousResult: List[Int], iterationValue: Int) => {
        if (previousResult.size == 0)
          previousResult :+ iterationValue
        else {
          val last: Int = previousResult.last
          if (iterationValue > last)
            previousResult :+ iterationValue
          else {
            previousResult.init :+ iterationValue :+ last
          }
        }
      }
      );
      val last: Int = subList.last
      bubbleSort(subList.init) :+ last;
    }
  }

  def main(args: Array[String]) {

    val tobeSort = List(6, 5, 3, 1, 8, 7, 2, 4);
    println(bubbleSort(tobeSort));

  }

}