基數排序

基數排序

       基數排序(Radix sort)原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。屬於一種分配模式排序方式. 基數排序法依比較的方向可分為最有效鍵優先(Most Significant Digit First, MSD)和最無效鍵優先 (Least Significant Digit First, LSD)兩種，MSD法是從最左邊的位數開始比較，而LSD則是從最右邊的位數開始比較。

C# 語法

合併排序

合併排序

      合併排序(Merge sort) 使用分治法(Divide and Conquer)的演算法來實作。排序時需要額外的空間來處理。

      分治法: 建基於多項分支遞歸的一種很重要的算法範式。

      分治法之優點:

1.       將困難的問題簡化為容易實作的方式。
2.       提升程式效率。
3.       能夠平行處理。

C# 語法 

快速排序

快速排序

       快速排序(Quicksort）原理從數列中挑選一個基準點，大於基準的放一邊，小於的放一邊，如此循環最後可完成排序。

快速排序演算法的運作:

1. 數列中選擇一元素作為基準點。
2. 小於元素的移至基準的左邊，大於元素的移至右邊，相等的任意放。
3. 基準點左邊和右邊視為兩個數列，並重複過程直到剩下一個或零。

實作範例C#  語法

氣泡排序

氣泡排序

       氣泡排序（Bubble Sort）原理重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。

氣泡排序演算法的運作:

1. 比較相鄰的兩個元素，若前面的元素較大就進行交換。
2. 重複進行1的動作直到最後面，最後一個元素將會是最大值。
3. 重複進行1,2的動作，每次比較到上一輪的最後一個元素。
4. 重複進行以上動作直到沒有元素需要比較。

實作範例:

C# 語法

JAVA 語法

插入排序

插入排序

       插入排序（Insertion Sort）原理是通過構建有序序列，對於未排序數據，在已排序序列中從後 向前掃描，找到相應位置並插入，插入排序在實現上，通常採用in-place排序，因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間，在與已排序的部分比較時，利用指派的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。 

       排序的部分比較時，利用指派的方式將元素往右位移，來達到插入的效果，因為位移的關係需要有另一個變數來暫存最右邊的數值。

運算流程:   

1. 將未排序的部分最左邊元素儲存到暫存變數。 
2. 由後往前和已排序部分元素比較，若大則將該元素往右邊位移。 
3. 重複2的動作直到遇到不大於自己的元素，將暫存變數寫入在該元素之後；若都沒有則寫入在最前面。

實作範例

C# 語法

JAVA語法

選擇排序

選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法，概念是反覆從未排序的數列中取出最小的元素，加入到另一個的數列，結果即為已排序的數列。

選擇排序的主要優點與數據移動有關。元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。

實作範例:

C# 語法 

Java 語法 

排序演算法

排序演算法

排序演算法(Sorting algorithm)是一種能將一串資料依照特定排序方式進行排列的一種演算法，排序演算法的輸出必須遵守下列兩個原則

排序演算原則

I.           輸出結果為遞增序列（遞增是針對所需的排序順序而言）。

II.        輸出結果是原輸入的一種排列、或是重組。

排序演算法只是個統稱，最常見的分為:

1. 選擇排序法(Selection Sort) 
2. 插入排序法(Insertion Sort) 
3. 氣泡排序法(Bubble Sort) 
4. 快速排序法(Quick Sort) 
5. 合併排序(Merge Sort) 
6. 基數排序(Radix Sort)

排序演算法之穩定與不穩定

相同資料當中，經過排序後會產生先後順序的步驟，因此分為不穩定與穩定的呈面。

• 穩定性: 相同值的資料，排序後順序和排序前一樣。
• 不穩定: 相同值的資料，排序後順序不一定和排序前一樣。

演算法	穩定性	類型	資料結構
選擇排序	不穩定	選擇	陣列
	穩定		連結串列
插入排序	穩定	插入	陣列、連結串列
氣泡排序	穩定	交換	陣列
搖晃排序	穩定	交換	陣列
快速排序	不穩定	交換	陣列
合併排序	穩定	合併	陣列、連結串列
基數排序	穩定	分配	陣列、連結串列