實現類似於冒泡排序的排序方法

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 

我正的錯誤是在功能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]. 

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 

就像在模式匹配哈斯克爾將檢查衛兵自上而下和執行返回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]) 

注意，這可能甚至冒泡排序因爲所有的連接列表的標準極低效（這很可能會是最好追加到累加器列表的頭部，然後在必要時反轉）。這種實現非常幼稚，但相當簡潔，也許很有啓發性，但更多的是因爲它的粗糙性超過了任何積極的美德。