讓程序員抓狂的排序算法教學(xué)視頻
羅馬尼亞是一個(gè)愛(ài)跳舞的民族，如果你看過(guò)羅馬尼亞老電影《奇普里安.博隆貝斯庫(kù)》，那歡快悠揚(yáng)的舞曲之熾熱呵，非把你融化不可！
羅馬尼亞人愛(ài)跳舞，不僅體現(xiàn)在電影和節(jié)日中，你會(huì)發(fā)現(xiàn)舞蹈無(wú)處不在，即使是大學(xué)里的計(jì)算機(jī)課程中的排序算法教學(xué)，也被用舞蹈的形式表現(xiàn)出來(lái)。
羅馬尼亞Tirgu Mures地區(qū)的Sapientia大學(xué)就制作了一系列用民族舞蹈形式表現(xiàn)的各種排序算法的工作原理。下面就是這些視頻。
舞跳的很好，但教學(xué)效果如何，我很難評(píng)判，至少讓我對(duì)這幾種排序算法的效率產(chǎn)生了嚴(yán)重的懷疑。
排序算法：選擇排序法
選擇排序(Selection sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì)n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。
排序算法：希爾排序法
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
1.插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)， 效率高， 即可以達(dá)到線性排序的效率
2.但插入排序一般來(lái)說(shuō)是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
排序算法：冒泡排序法
冒泡排序（Bubble Sort，臺(tái)灣譯為：泡沫排序或氣泡排序）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
冒泡排序?qū)個(gè)項(xiàng)目需要O(n^2)的比較次數(shù)，且可以原地排序。盡管這個(gè)算法是最簡(jiǎn)單了解和實(shí)作的排序算法之一，但它對(duì)于少數(shù)元素之外的數(shù)列排序是很沒(méi)有效率的。
排序算法：快速排序法
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見(jiàn)。事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來(lái)。
排序算法：歸并排序法
歸并排序（Merge sort，臺(tái)灣譯作：合并排序）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
排序算法：插入排序法
插入排序（Insertion Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為***元素提供插入空間。
