使用haskell實作的快排代碼真的是相當簡潔,直覺,很有美感。相對于C系列語言來說,haskell寫算法的時候更關注算法本身是什麼樣子而不是怎麼去實作這個算法,這點真的很棒。
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallPart = quicksort [a | a <- xs, a <= x]
bigPart = quicksort [a | a <- xs, a > x]
in smallPart ++ [x] ++ bigPart
作為對比,下面的是C的實作,在表達能力上,高下立判。
void quick_sort(int *A, int L, int R) {
if (R <= L) return;
int key = A[L], u = L, v = R;
while (L < R) {
while (L < R && A[R] >= key) --R;
A[L] = A[R];
while (L < R && A[L] <= key) ++L;
A[R] = A[L];
}
A[L] = key;
quick_sort(A, u, L - 1);
quick_sort(A, L + 1, v);
}