实现类似于气泡排序的排序方法

Question

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

伪代码如下所示：

获取
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

我得到的错误是

函数堆栈气泡中的非穷举模式'

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

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].

Answer 1

解决此问题的最简单方法可能是使用防护和简单的递归，例如：

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]

此实现没有显式"标记"元素为已移动，但这不是必需的。

Answer 2

您

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

Answer 3

我开始编写更正版本，但是当我这样做时，这个问题得到了回答。无论如何，为了演示，我将在此处包含它：

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])

请注意，即使按照气泡排序的标准，由于所有列表串联，这可能效率极低（最好附加到累加器列表的头部，然后在必要时反转）。这种实现非常幼稚，但相当简洁，也许是有启发性的，尽管更多的是因为它的公然粗糙而不是任何积极的美德。