
何謂排序(Sorting)
將一組資料依使用者的需要予以重新安排其順序。
資料結構,排序法可分兩類
第一類:內部與外部排序法
- 內部排序法(Internal Sort)
[定義]指要排序的資料全部都是在主記憶體(RAM)內完成。又稱陣列排序。
[適用時機]資料量較少者
- 外部排序法(External Sort)
[定義]排序的工作是在輔助記憶體內完成。又稱檔案排序。
[適用時機]資料量較大者
第二類:穩定與不穩定排序法
- 穩定排序法(Stable Sorting)
[定義]如果鍵值相同之資料在排序後的相對位置和排序前相同時,稱為穩定排序
- 不穩定排序法(UnStable Sorting)
[定義]如果鍵值相同之資料在排序後的相對位置和排序前不相同時,稱為不穩定排序
排序法種類
- 氣泡排序法(Bubble Sort)將兩個相鄰的資料相互做比較,若比較時發現次序不對,則將兩資料互換,依次由上往下比,而結果則會依次由下往上浮起,如氣泡般。
- 選擇排序法(Selection Sort)在找到比目前大或小的數字時,先記錄其位置或索引值,待確定後再進行資料的交換。
- 插入排序法(Insertion Sort)每一次往後拿一筆記錄,插入到前面已經排序好的記錄。
- 快速排序法(Quick Sort)又稱分割交換排序法,先在資料中找到一個中間值,把小於中間值的資料放在左邊而大於中間值的資料放在右邊,再以同樣的方式分別處理左右兩邊的資料,直到完成為止。
- 堆積排序法(Heap Sort)利用堆積樹的樹根移走,再將剩下的節點重新建立堆積樹,重排依次就表示完成一個值的排序,直到剩下最後一個節點時,排序也完成。
- 謝耳排序法(Shell Sort)是插入排序法演進而來,目的是用來減少插入排序法中元素搬移的次數,增快排序的速度。
- 合併排序法(Merge Sort)合併排序適用於內部排序和外部排序
- 基數排序法(Radix Sort)