1

我试图弄清楚如何实现一种类似于冒泡排序但在某些方面有所不同的排序方法。

伪代码将是这样的：

  1. 获取列表并获取列表中的第一个元素
  2. 如果它旁边的元素更小，则交换元素
  3. 否则将元素标记为已移动并重复直到所有元素都被标记

以下是我对实现这个问题的想法：

sortElement [] elm= []
sortElement [x] elm= [x]
sortElement lis@(x:y:xs) elm = 
--first if is to find the element in the list that i want to move
if elm /=x  
then x:sortElement(y:xs) elm 
else if x > y then y:sortElement(x:xs) elm 
else lis

stackBubble lis = stackBubble' lis lis

stackBubble' [] [] = [] 
stackBubble' [x] [] = [x]
stackBubble' [] [x] = []
stackBubble' lis@(x:xs) lis1@(x1:xs1) = do 

sortElement(stackBubble' lis xs1) x1

我得到的错误是

函数 stackBubble 中的非详尽模式'

如果我喜欢其他地方的建议：

sortElement(x:stackBubble' xs xs1) x1

当我想得到这样的东西时，我会在一次迭代后得到一个完全排序的列表：

[4,2,7,1] => iterating 4 [2,4,7,1], after iterating all the elements [2,4,1,7].
4

3 回答 3

2

您收到错误是因为stackBubble'当一个参数为空而另一个参数有多个元素时未指定结果。

于 2012-06-12T01:59:04.433 回答
2

我开始编写一个更正的版本，但是当我这样做时，问题得到了回答。为了演示起见，无论如何我都会在这里包含它：

bubbleSort l =
  bSort l []
  where bSort []        acc = acc
        bSort [x]       acc = acc ++ [x]
        bSort (x:y:xys) acc
          | x > y     = bSort (acc ++ (y:x:xys)) []
          | otherwise = bSort (y:xys) (acc ++ [x])

请注意，即使按照冒泡排序的标准，这也可能是非常低效的，因为所有列表连接（很可能最好附加到累加器列表的头部，然后在必要时反转）。这种实现非常幼稚，但相当简洁，也许具有启发性，尽管更多的是因为它的粗鲁比任何积极的美德都明显。

于 2012-06-12T02:35:50.447 回答
2

解决这个问题的最简单方法可能是使用守卫和简单的递归，例如：

bubble :: Ord a => [a] -> [a]
bubble (x:y:xs) | x > y = y : bubble (x : xs)
                | otherwise = x : bubble (y : xs)
bubble x = x

你已经覆盖了警卫吗？以防万一你没有，我会简短地解释一下。守卫的语法是

| (expression that evaluates to Bool) = code

就像在模式匹配中一样，Haskell 会从上到下检查守卫并执行第一个返回 true 的守卫。otherwise是刚刚定义为的“失败案例” True。

所以逐行浏览代码：

bubble (x:y:xs) | x > y = y : bubble (x : xs)

我们将列表分成 x:y:xs 并运行第一个守卫，它检查 y 是否小于 x，如果是 y，则将其附加到我们正在构建的结果列表中，然后使用 (x : xs) 再次调用气泡。

                | otherwise = x : bubble (y : xs)

第二个守卫总是返回 True，将 x 保持在它的位置并再次调用气泡，列表仍然保持相同的顺序。
最后一行只返回最后一个元素，或者如果您使用空列表调用该函数，则返回一个空列表。

假设示例列表 [4,2,5,1] 执行将如下所示：

1: 2 is smaller than 4 -> 2 : bubble [4,5,1]
2: 5 is not smaller than 4 -> 2 : 4 : bubble [5,1]
3: 1 is smaller than 5 -> 2 : 4 : 1 : bubble [5]
4: end of list -> 2 : 4 : 1 : 5 -> [2,4,1,5]

此实现没有明确地将元素“标记”为已移动，但这不是必需的。

于 2012-06-12T10:56:27.013 回答