可視化排序演算法

本文所用代碼已整合進SortAlgorithm.m,下載請到GitHub - GalAster/BiGridGenerator

---------------------------------------------------------------------------------------------------------------------------

想給萌新演示下各種排序演算法,直觀的顯示出過程,然後TableForm一下,或者M大這裡給出的效果差不多就行了http://www.matrix67.com/blog/archives/1763

想了下思路應該就是給出過程表直接ArrayPlot就行了.....然後問題來了,排序過程表怎麼搞出來的呢?內存軌跡是指什麼?可能是Trace的意思吧...寫個快排試試...

QS[{x_,xs___}]:=Join[QS@Select[{xs},#<=x&],{x},QS@Select[{xs},#>x&]];QS[{}]={};Trace@QS@RandomSample@Range@10

快排倒是不難寫,就兩行,可是怎麼從這個見鬼的堆棧中把過程提取出來咧???

巭孬嫑夯搞模式匹配.......我本來就不怎麼會寫規則變換,瞎配了半天決定改寫過程式....

然後寫了半天發現,我好像確實不怎麼會寫過程式的演算法,然後發現學起來確實有點小難,而且排序演算法和排序過程演算法還是有點區別的....寫了一整天就寫出了冒泡,插入和雞排,希爾以及快排5種演算法....捂臉,堆排桶排統統不會寫.....歡迎各位把其他排序過程演算法Pull給我...

(雞排不是吃的那個啦...說的我都有點餓了...)

從左到右依次是,冒泡排序,雞尾酒排序,希爾排序,插入排序和快速排序.

同等比例下越寬說明排序越快.....

網上找找可視化方案看見了這個sortvis.org - sorting algorithm visualisation

哇,好炫酷,我們來仿一個.大概就是這個效果:

非常直觀的顯示出了各個演算法的排序過程,交換次數越少就越快....

但是我還是不會寫剩下幾個排序,研究點獵奇的排序演算法好了.第一個猴排和量子猴排.

可以,這很量子....這個是來搞笑的吧,下一個....

接下來來個正經的,豬排,越說越餓了,口誤,是珠排演算法....

我研究了下,珠排其實包含了四種演算法,分別對應不同的物理假設.

力的作用是否是瞬時的?

物體速度能否是無限大?

根據這兩個假設可以分成四種物理模型:延遲勻速,延遲光速,瞬時勻速以及瞬時光速.

前三種都是複雜度,最後一種是複雜度.....

我們來分步看一下,簡單的說力瞬時性就是碰到物體會不會卡一下,速度無限大就是直接降到底.兩個假設都服從自然直接一步排序完成...

---------------------------------------------------------------------------------------------------------------------------

是否存在一種完美排序演算法使得對任意亂序的比較次數最少?顯然是有的,下一個...

如何構造出這種演算法呢?

演算法學家們發明了排序網路,這玩意兒很容易理解

兩根線一個比較器.下面比上面大就換,反之就不換.

然後很多根線,放上一個個比較器就組成了排序網路.

有的排序演算法和有的排序網路等價,比如第二個排序網路叫插入排序網路,等價插入排序演算法.相近最接近完美排序網路的是Batcher網路.

排序網路有兩個指標,比較器個數和比較深度,前者表示單線程運行時的需要的時間,後者表示允許無限並行時需要的時間.

Batcher網路個數是,深度是.無論單線程還是並行秒了所有排序演算法....比Batcher更優的只有搜索出來的最優網路和理論上存在的完美網路了.

很不幸的是完美排序網路的證明是個coNP問題,9和10的證明直到2014年才完成....啥,你問我怎麼證的?窮舉唄...頂多聰明點的窮舉....不過其實構造的話很早以前就構造出來的,沒法指著他說這個一定是最優而已.......和證明三階魔方至多需要20步還原一樣,沒全部搜索完之前只能叫猜想.

這方面的論文好像也不是很多...可能是這玩意兒構造起來比較麻煩吧,等你構造完我都排序排完一萬遍了.....似乎也沒啥大規模需要重複排序的應用場景,也就數學上有點研究意義了....

https://arxiv.org/pdf/1405.5754v3.pdf

https://arxiv.org/pdf/1310.6271v2.pdf

推薦閱讀：