Clojure 快速排序 快排
快速排序（Quicksort）是一種優(yōu)秀的排序算法，這個(gè)就不多介紹了。
本文用最通俗的語言講解快速排序的原理，以及如何使用 Clojure 實(shí)現(xiàn)快速排序。
首先快速排序的原理很簡單，不要被那些專業(yè)名詞嚇傻了。什么分治法，什么分析時(shí)間復(fù)雜度，又搞什么兩個(gè)指針一會(huì)兒這邊移動(dòng)一會(huì)兒交換一會(huì)兒那邊移動(dòng)。這些對(duì)你理解快排的原理毫無幫助，反而會(huì)阻礙你理解快排的本質(zhì)。
快排的本質(zhì)就一句話：
從需要排序的數(shù)里面隨便找出一個(gè)，然后，把比這個(gè)數(shù)小的放在這個(gè)數(shù)左邊，比這個(gè)數(shù)大的放在這個(gè)數(shù)右邊，一樣大的和這個(gè)數(shù)放在一起，最后，左右兩邊各自重復(fù)上述過程，直到左邊或右邊只剩下一個(gè)數(shù)（或零個(gè)數(shù)）無法繼續(xù)為止。
我們可以明顯的看出這是一個(gè)遞歸定義。
先看靈魂畫手的示意圖：
假如我們要給這五個(gè)數(shù)字排序，首先我們先從中隨意選取一個(gè)數(shù)字，比如 4。
按照規(guī)則，比 4 大的數(shù)字都放在右面，比 4 小的數(shù)字都放在左面。所以一次過后變成了這樣。
按照規(guī)則，左右兩面各自重復(fù)上述步驟，直到數(shù)量為一個(gè)以下無法繼續(xù)。右面已經(jīng)只有一個(gè)了，所以不用重復(fù)了。左面重復(fù)上述步驟。
還是隨機(jī)從中選取數(shù)字，這次我們選擇 2。把大于 2 的放在右面，小于 2 的放在左面。
左右兩邊都已經(jīng)是一個(gè)，不用繼續(xù)了，排序結(jié)束。
那在 Clojure 中如何實(shí)現(xiàn)這種算法呢？
我們直接看代碼：
(defn quick-sort
[nums]
(if (< (count nums) 2)
nums
(concat
(quick-sort (filter #(< % (first nums)) nums))
(filter #(= % (first nums)) nums)
(quick-sort (filter #(> % (first nums)) nums)))))
這段代碼十分淺顯易懂。首先定義一個(gè)函數(shù)，名叫 quick-sort，它接受一個(gè)數(shù)字集合。
如果集合中元素的數(shù)量小于 2，那么直接返回這個(gè)集合。這符合快排的定義。
如果元素?cái)?shù)量大于等于 2，我們選取集合的第一個(gè)元素作為分割的標(biāo)準(zhǔn)（定義中是隨機(jī)選取，所以在這里可以根據(jù)你的喜好和需要進(jìn)行選取），使用 filter 函數(shù)篩選出小于、大于、等于，三種情況，最后使用 concat 函數(shù)進(jìn)行連接。
一切都是這么自然。
我們來看一下實(shí)際運(yùn)行情況。
首先要生成一些隨機(jī)數(shù)以供排序。這個(gè)我們寫一個(gè)函數(shù)來產(chǎn)生：
(defn rand-n-m [n m]
"從 1 到 m 范圍內(nèi)，隨機(jī)產(chǎn)生 n 個(gè)數(shù)字"
(repeatedly n #(+ 1 (rand-int m))))
生成 1 到 100 內(nèi)的隨機(jī)數(shù) 10 個(gè)：
=> (println (rand-n-m 10 100))
(25 42 4 34 8 35 93 47 58 16)
還不錯(cuò)，我們來看看排序算法工作如何：
=> (println (quick-sort (rand-n-m 10 100)))
(10 16 18 35 41 47 57 83 86 90)
刷的一下就出來了。
不過就 10 個(gè)數(shù)字顯露不出我們快排的威力，這次我們上多點(diǎn)數(shù)字。并在外側(cè)套上 time 統(tǒng)計(jì)運(yùn)行時(shí)間。
=> (time (quick-sort (rand-n-m 10000 100000)))
"Elapsed time: 144.926382 msecs"
旁邊的冒泡排序依然在吭哧吭哧算著呢...
P.S..
為啥 C 、Java 等一批語言寫快排怎么搞了一個(gè)數(shù)組兩個(gè)指針循環(huán)過來循環(huán)過去？
這個(gè)你們自己思考，聲明式編程和命令式編程的區(qū)別。
