三部分元组的冒泡排序

Question

我正试图实现泡沫排序排序按优先级排序我的列表。例如，列表的格式如下，其中第3个元素为优先级:

  [("Ted", 100, 3), ("Boris", 100, 1), ("Sam", 100, 2)]

我已经尝试了下面的标准冒泡排序方法，但是这不起作用。任何建议都将不胜感激。

bubbleSort :: (Ord t) => [t] -> [t]
bubbleSort a = loop (length a) bubble a
bubble :: (Ord t) => [t] -> [t] 
bubble (a:b:c) | a < b = a : bubble (b:c)
           | otherwise = b : bubble (a:c)
bubble (a:[]) = [a] 
bubble [] = []
loop :: (Num a, Ord a) => a -> (t -> t) -> t -> t
loop num f x | num > 0 =  loop (num-1) f x'
         | otherwise = x
         where x' = f x

Answer 1

正如luqui所暗示的那样，通常不直接实现Ord约束版本的排序算法，而是使用自定义比较的更通用的排序算法:

bubbleSortBy :: (t->t->Ordering) -> [t] -> [t]
bubbleSortBy cmp a = loop (length a) bubble a
 where
       bubble :: (Ord t) => [t] -> [t] 
       bubble (a:b:c) = case cmp a b of
                          LT -> a : bubble (b:c)
                          _  -> b : bubble (a:c)
       bubble l = l
loop :: Integral a    -- (Num, Ord) is a bit /too/ general here, though it works.
   => a -> (t -> t) -> t -> t
loop num f x | num > 0    = loop (num-1) f x'
             | otherwise  = x
         where x' = f x

Ord版本从这里简单地遵循:

bubbleSort :: (Ord t) -> [t] -> [t]
bubbleSort = bubbleSortBy compare

，但通常直接使用通用版本更实用，就像在你的例子中

import Data.Function(on)
sorted_priority3rd = bubbleSortBy ( compare `on` (a,b,c) -> (c,a,b) )

的作用是，在每次比较之前改变实参的顺序。显然，这使得气泡排序更加缓慢;通常你会选择

import Data.List (sortBy)   -- this is a proper 𝑂(𝑛 log 𝑛) sorting algorithm
sorted_by3rd = sortBy ( compare `on` (a,b,c) -> c )