Noob's Space

六分鐘看完 15 種排序演算法,其中幾種好療癒

常常聽過各式各樣的排序演算法,但你真的知道這些演算法是怎麼排序的嗎?

快來看看 Timo Bingmann 做的六分鐘小短片,一次看懂十五個排序演算法!

排序法

影片中用到的十五種排序法:

選擇排序法 (Selection Sort):一種較直觀的排序演算法,將資料分為已排序和未排序兩個部分,一直從未排序找出最大和最小值放入已排序的部分,直到未排序資料用完為止。

插入排序法(Insertion Sort):一樣將資料分為已排序和未排序兩個部分,依序將未排序的第一筆插入已排序中的適當位置。

快速排序法(Quick Sort – LR ptrs):選擇一個基準值,把比基準值大的都放右邊、比基準值小的都放左邊。接著針對左邊的部分和右邊的部分各進行一次以上動作(遞迴)。

合併排序法(Merge Sort):將兩個已排序的序列合併成一個序列。

堆積排序法(Heap Sort):堆積排序法算是選擇排序法的改良,透過使用二元樹的技巧,減少選擇排序中的比較次數,進而減少排序時間。

基數排序法-由右至左(Radix Sort – LSD):將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零。然後,從最低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。

影片的這個部分看起來蠻療癒的 XD

基數排序法-由左至右(Radix Sort – MSD)

同上,只是由右往左比較。

std::sort:C++ 中提供的升序排序法。

std::stable_sort:C++ 中提供的排序法,但能夠保證相等的元素不更動原先的順序。

希爾排序法(Shell Sort):希爾排序法為插入排序法的改良,一樣將資料分為已排序和未排序兩個部分,但每次排序時會利用前次排序的結果。

泡泡排序法(Bubble Sort):一次比較兩個元素,遇到順序錯誤就交換過來,一直到沒有需要交換的數列。這個演算法名字的由來是因為越小的元素會經由交換慢慢浮到數列的頂端。

雞尾酒排序法、搖晃排序法(Cocktail Shaker Sort):又叫雙向氣泡排序法,為氣泡排序法的改良。將資料分成未排序、已排序兩個部分,並利用氣泡排序法將未排序中的最大值移動到未排序的最右邊、未排序中的最小值移動到未排序的最左邊。

地精排序法(Gnome Sort):由左往右檢查,遇到比較小的就把該值從最左邊開始比較,並放到對的地方。

分段排序網路(Bitonic Sort):一種不依賴數據的排序方法(?),待補充。

但這部分也很可愛 XD

猴子排序法 (Bogo Sort):一個既不實用又原始的排序法,原理等同將一堆卡片拋起,落在桌上後再檢查卡片是否已整齊排列好,若非就再拋一次。基本上來亂的,但概念和無線猴子定理有點類似(指一群猴子隨機亂打而打出一份 Java 程式碼的機率極低,但不是零)。

影片來源:Yes I’m A Programmer

你可能會有興趣......?

廣告