4.1排序法簡介

一、氣泡排序法

Bubble Sort 的方式是從陣列的最前面開始，一次比較陣列中兩兩相鄰的元素，然後根據大小將它們調換順序，大的移到後面：

• 當我們比較過所有元素一次後，可以確保數值最大的元素在最後面

• 接著扣掉陣列中的最後一個元素（因為已經確定它是最大的），接著重複上面的步驟進行兩兩比較

• 重複上述動作，直到排序完畢。假設這個陣列有 6 (N)個元素一共需重複這個動作 5 次（N - 1）才能確保排序完畢。

實作排序法：

假設有一整數陣列為data[n]，n為陣列長度

for(int i=n-1;i>=0;i--){

for(int j=0;j<i;j++){

if(data[j+1]<data[j])

swap(data[j+1],data[j]) ;

}

}

二、其他排序法

• • 選擇排序法(Selection Sort)

  • 一一掃瞄未排序資料，找出最大值(or最小)

  • 將最大值加入已排序的資料中

  • 插入排序法(Insertion Sort)

  • 依序由未排序的資料中選一筆資料

  • 一一掃瞄已排序資料，將選取的資料插入正確位置

  • 氣泡排序法(Bubble Sort)

  • 對未排序資料兩兩比對掃瞄

  • 兩兩比對時會將未排序的最大值，介由Swap移到未排序資料中的最右邊

  • 謝爾排序法(Shell Sort)

  • 將一維陣列看待成二維陣列

  • 依序對二維陣列的每一行作排序

  • 搖晃排序法(Shaker Sort)

  • 雙向的氣泡排序法

  • 每回合都會將未排序資料中的最大值移到最右邊，最小值移到最左邊

  • 快速排序法(Quick Sort)

  • 將比基準值(Pivot)小的數值移到左邊，比基準值大的數值移到右邊

  • 對基準值的左、右子數列遞迴作相同動作

  • 合併排序(Merge Sort)

  • 將數列對分成兩個子數列，並遞回對分

  • 對分至只有一個元素時，將元素回傳合併

  • 堆積排序(Heap Sort)

  • 利用堆積樹(Heap Tree)的性質來排序

  • 最大堆積樹(Max Heap Tree)的根節點一定是最大值，一一與最後一個樹葉節點交換後，取出加入已排序數列

  • 將原來的樹重新調整為最大堆積樹

  • 基數排序(Radix Sort)

  • 可多鍵值排序

  • 將資料一一分類後再合併