淺談排序:資料結構中的基本觀念,輕鬆易懂!

資料結構

何謂排序(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)

發佈留言