排序:將一串未經過排序的數字，經過特殊的排序規則，形成一筆升序或降序的線性關係。
排序有分為:
1.穩定或不穩定
2.內部排序法或外部排序法
其中初階排序法的average time complexity分別為:O(n²)，且皆為內部排序法
插入排序法(Insertion sort)
1.將一筆紀錄，插入到i筆紀錄之中，使i+1筆的紀錄成為一筆排序好的資料
過程如下:
| init. | 3 | 2 | 4 | 5 | 1 |
| step 1 | 2 | 3 | 4 | 5 | 1 |
| step 2 | 2 | 3 | 4 | 5 | 1 |
| step 3 | 2 | 3 | 4 | 5 | 1 |
| step 4 | 1 | 2 | 3 | 4 | 5 |
1.時間複雜度:
最好(1,2,3,4,5):O(n)
因為只需要n-1次的比較
最差(5,4,3,2,1,):O(n²)
因為有n個數字，每個數字都需要移動(n-1)次->n(n-1)
2.為一個穩定(Stable)的排序
選擇排序法(Selection sort)
:分為兩步驟
1.在n筆未經排序過的數字中選擇最小的數字與第i筆交換
2.在剩餘的n-1筆中再次挑選一筆最小的值，與第i+1筆的值交換，重複此動作直到(i=n為止)
過程如下:
| init. | 3 | 2 | 4 | 5 | 1 |
| step 1 | 1 | 2 | 4 | 5 | 3 |
| step 2 | 1 | 2 | 4 | 5 | 3 |
| step 3 | 1 | 2 | 3 | 5 | 4 |
| step 4 | 1 | 2 | 3 | 4 | 5 |
1.時間複雜度:
最好最差平均都為:O(n²)
因為有n個數字，每個數字都需要比較(n-1)次->n(n-1)
2.為一個不穩定(Unstable)的排序
舉例:5,1,3,5+,4
1::1,5,3,5+,4
2::1,3,5,5+,4
3::1,3,4,5+,5
做到這會發現原本5在5+之前，但到了step3之後5跑到5+之後，因此為不穩定的排序
氣泡排序法(bubble sort)
:逐一比較相鄰兩筆的資料，如果第i筆的資料大於第i+1筆，則兩者交換。
過程如下:
| init. | 3 | 2 | 4 | 5 | 1 |
| step 1 | 2 | 3 | 4 | 1 | 5 |
| step 2 | 2 | 3 | 1 | 4 | 5 |
| step 3 | 2 | 1 | 3 | 4 | 5 |
| step 4 | 1 | 2 | 3 | 4 | 5 |
細看step1的過程:
1::3,2,4,5,1
2::比較3,2->交換->2,3,4,5,1
3::比較3,4->不須交換
4::比較4,5->不須交換
5::比較5,1->交換->2,3,4,1,5 (結束)
1.時間複雜度為:
最佳O(n)
因為以排序好的數字只需要比較(n-1)次
最差:O(n²)
2.為一個stable sort
