函数scala中的选择排序

作为 starblue already said ,需要一个函数来计算列表的最小值,并返回删除该元素的列表。下面是类似的递归实现(我相信 foldl 是标准库中的尾部递归),我试图使其尽可能地正常工作。它返回一个列表,其中包含原始列表的所有元素(但有点颠倒,请参阅下面的解释),最小值作为标题。

def minimum(xs: List[Int]): List[Int] =
  (List(xs.head) /: xs.tail) {
    (ys, x) =>
      if(x < ys.head) (x :: ys)
      else            (ys.head :: x :: ys.tail)
  }

这基本上是一个折叠,从包含 xs 如果的第一个元素 XS 小于该列表的头,我们将其预先附加到列表中 ys .否则,我们将它添加到列表中 YS 作为第二个元素。因此,我们递归地将列表折叠成一个新的列表,其中包含作为头的最小元素和包含 XS (不一定以相同的顺序)以最小值去除,作为尾部。请注意,此函数不会删除重复项。

创建这个助手函数之后,现在很容易实现选择排序。

def selectionSort(xs: List[Int]): List[Int] =  
  if(xs.isEmpty) List()
  else {
    val ys = minimum(xs)
    if(ys.tail.isEmpty) 
      ys
    else
      ys.head :: selectionSort(ys.tail)
  }

不幸的是,这个实现是 不 尾部递归,因此它将放大大列表的堆栈。无论如何,您不应该对大列表使用o(n^2)排序,但是…如果实现是尾部递归的,那就更好了。我会想办法…我认为它会像一个折叠的实现。

尾部递归!

为了使其尾部递归,我在函数编程中使用了非常常见的模式——一个累加器。它有点向后工作,因为现在我需要一个名为 maximum 基本上和 minimum ,但对于最大元素-它的实现与最小值一样精确,但使用 > 而不是 < .

def selectionSort(xs: List[Int]) = {
  def selectionSortHelper(xs: List[Int], accumulator: List[Int]): List[Int] =
    if(xs.isEmpty) accumulator
    else {
          val ys = maximum(xs)
          selectionSortHelper(ys.tail, ys.head :: accumulator)
    }

  selectionSortHelper(xs, Nil) 
  }

编辑 :更改了答案,使助手函数作为选择排序函数的子函数。

它基本上将极大值累积到一个列表中,最终作为基本情况返回。您还可以通过替换看到它是尾部递归的 accumulator 通过 throw new NullPointerException -然后检查堆栈跟踪。

这里有一个使用累加器的逐步排序。左侧显示列表 XS 当右手边显示 蓄电池 . 最大值在每一步用一个星表示。

64* 25 12 22 11  ------- Nil
11 22 12 25*     ------- 64
22* 12 11        ------- 25 64
11 12*           ------- 22 25 64
11*              ------- 12 22 25 64
Nil              ------- 11 12 22 25 64

以下显示了逐步折叠以计算最大值:

maximum(25 12 64 22 11)

25 :: Nil         /: 12 64 22 11  -- 25 > 12, so it stays as head
25 :: 12          /: 64 22 11     -- same as above
64 :: 25 12       /: 22 11        -- 25 < 64, so the new head is 64
64 :: 22 25 12    /: 11           -- and stays so
64 :: 11 22 25 12 /: Nil          -- until the end

64 11 22 25 12

这里是选择排序(通用版本)的另一个实现。

def less[T <: Comparable[T]](i: T, j: T) = i.compareTo(j) < 0

def swap[T](xs: Array[T], i: Int, j: Int) { val tmp = xs(i); xs(i) = xs(j); xs(j) = tmp }

def selectiveSort[T <: Comparable[T]](xs: Array[T]) {
    val n = xs.size
    for (i <- 0 until n) {
        val min = List.range(i + 1, n).foldLeft(i)((a, b) => if (less(xs(a), xs(b))) a else b)
        swap(xs, i, min)
    }
  }     

您需要一个辅助函数来进行选择。它应该返回最小元素和列表中删除元素后的其余部分。

在函数样式中进行选择排序时应该会遇到问题,因为它是一种就地排序算法。根据定义,就地不起作用。

你面临的主要问题是你不能 掉期 元素。这就是为什么这一点很重要。假设我有一个清单 ₀ …一 _X …一 _n ,在哪里 _X 是最小值。你需要一个 _X 离开,然后组成一个列表(a _零 ……一 _X-1 一 _{X+ 1} 一 _n )问题是你必须 复制 元素A _零 到A _X-1 ,如果您希望保持纯粹的功能性。其他的功能数据结构,特别是树,可以有比这更好的性能,但基本的问题仍然存在。

我认为以功能性风格进行选择是合理可行的,但是正如丹尼尔所指出的,它有很好的机会表现得很糟糕。

我只是试着写一个函数气泡排序,作为一个稍微简单和退化的选择排序案例。以下是我所做的,这暗示了你可以做什么:

define bubble(data)
  if data is empty or just one element: return data;
  otherwise, if the first element < the second,
    return first element :: bubble(rest of data);
    otherwise, return second element :: bubble(
      first element :: (rest of data starting at 3rd element)).

一旦完成递归,最大的元素就在列表的末尾。现在,

define bubblesort [data]
  apply bubble to data as often as there are elements in data.

完成后,您的数据确实会被排序。是的,这很可怕,但是我对这个伪代码的Clojure实现是有效的。

仅仅关注第一个或两个元素,然后将其余的工作留给一个重复的活动,这是一种lisp-y、功能性y的方法来完成这类事情。但是一旦你的头脑习惯了这种想法,就有了更明智的方法来解决这个问题。

我建议实现合并排序:

Break list into two sub-lists, 
either by counting off half the elements into one sublist 
  and the rest in the other,
or by copying every other element from the original list 
  into either of the new lists.

Sort each of the two smaller lists (recursion here, obviously).

Assemble a new list by selecting the smaller from the front of either sub-list
until you've exhausted both sub-lists.

递归就是其中的一部分,我看不出一种巧妙的方法可以使算法尾部递归。不过,我认为这是O(log-2)的时间,也不会给堆栈带来过高的负载。

玩得开心,祝你好运!

感谢上面的提示,他们非常鼓舞人心。这是选择排序算法的另一种功能方法。我试着基于以下想法:找到一个最大/最小值可以很容易地通过 min(A)=if A=Nil ->Int.MaxValue else min(A.head, min(A.tail)) . 第一分钟是列表的最小值,第二分钟是两个数字的最小值。这很容易理解,但不幸的是尾部不是递归的。使用Accumulator方法可以这样转换min定义,现在在正确的scala中:

def min(x: Int,y: Int) = if (x<y) x else y

def min(xs: List[Int], accu: Int): Int = xs match {
    case Nil => accu
    case x :: ys => min(ys, min(accu, x))
}

(这是尾部递归)

现在需要一个Min版本,它返回一个不包含Min值的列表。以下函数返回一个列表,其头部是最小值,尾部包含原始列表的其余部分:

def minl(xs: List[Int]): List[Int] = minl(xs, List(Int.MaxValue))

def minl(xs: List[Int],accu:List[Int]): List[Int] = xs match {
// accu always contains min as head
    case Nil => accu take accu.length-1
    case x :: ys => minl(ys, 
        if (x<accu.head) x::accu else accu.head :: x :: accu.tail )
}

使用此选择排序可以以递归方式编写尾部,如下所示:

def ssort(xs: List[Int], accu: List[Int]): List[Int] = minl(xs) match {
    case Nil => accu
    case min :: rest => ssort(rest, min::accu)
}

(颠倒顺序)。在一个包含10000个列表元素的测试中,该算法仅比通常的命令式算法慢4倍。

尽管,在编写scala时,我习惯于使用函数式编程(通过组合器或递归)而不是命令式编程(通过变量和迭代),但这次,对于这个特定的问题,老式的命令式嵌套循环会导致更简单和更高性能的代码。

我不认为退回命令式对于某些问题是一个错误,例如排序算法,它通常将输入缓冲区转换到位,而不是生成一个新的集合。

我的解决方案是:

package bitspoke.algo

import scala.math.Ordered
import scala.collection.mutable.Buffer

abstract class Sorter[T <% Ordered[T]] {

  // algorithm provided by subclasses
  def sort(buffer : Buffer[T]) : Unit

  // check if the buffer is sorted
  def sorted(buffer : Buffer[T]) = buffer.isEmpty || buffer.view.zip(buffer.tail).forall { t => t._2 > t._1 }

  // swap elements in buffer
  def swap(buffer : Buffer[T], i:Int, j:Int) {
    val temp = buffer(i)
    buffer(i) = buffer(j)
    buffer(j) = temp
  }
}


class SelectionSorter[T <% Ordered[T]] extends Sorter[T] {
  def sort(buffer : Buffer[T]) : Unit = {
    for (i <- 0 until buffer.length) {
      var min = i
      for (j <- i until buffer.length) {
        if (buffer(j) < buffer(min))
          min = j
       }
       swap(buffer, i, min)
     }
  }
}

如您所见,实现参数多态性,而不是使用 java.lang.Comparable 我更喜欢 scala.math.Ordered 和scala视图边界,而不是上界。由于原始类型的scala隐式转换为丰富的包装器,这当然是可行的。

您可以编写如下客户端程序:

import bitspoke.algo._
import scala.collection.mutable._

val sorter = new SelectionSorter[Int]
val buffer = ArrayBuffer(3, 0, 4, 2, 1)
sorter.sort(buffer)

assert(sorter.sorted(buffer))

scala中选择排序的简单函数程序

def selectionSort(list:List[Int]):List[Int] = {
  @tailrec
  def selectSortHelper(list:List[Int], accumList:List[Int] = List[Int]()): List[Int] = {

    list match {
      case Nil => accumList
      case _ => {
        val min  = list.min
        val requiredList = list.filter(_ != min)
        selectSortHelper(requiredList, accumList ::: List.fill(list.length - requiredList.length)(min))
      }
    }
  }
  selectSortHelper(list)
}

您可能想尝试用递归替换while循环,所以有两个地方可以创建新的递归函数。

这将开始消除一些var。

这对我来说可能是最艰难的一课,我试图向外交政策迈进。

我不愿意在这里展示解决方案,因为我认为你最好先试试。

但是,如果可能的话,您应该使用尾部递归,以避免堆栈溢出的问题(如果您正在排序一个非常非常大的列表)。

以下是我对这个问题的看法: SelectionSort.scala

def selectionsort[A <% Ordered[A]](list: List[A]): List[A] = {
  def sort(as: List[A], bs: List[A]): List[A] = as match {
    case h :: t => select(h, t, Nil, bs)
    case Nil => bs
  }

  def select(m: A, as: List[A], zs: List[A], bs: List[A]): List[A] = 
    as match {
      case h :: t => 
        if (m > h) select(m, t, h :: zs, bs)
        else select(h, t, m :: zs, bs)
      case Nil => sort(zs, m :: bs)
    }

  sort(list, Nil)
}

有两个内部功能: sort 和 select 表示原算法中的两个循环。第一个函数 分类 遍历元素并调用 选择 为他们中的每一个。当源列表为空时,返回 bs 结果列表,最初 Nil . 这个 分类 函数尝试在源列表中搜索最大(不是最小,因为我们以可逆顺序构建结果列表)元素。假设最大值是 head 默认情况下,然后用适当的值替换它。

这是scala中选择排序的100%功能实现。