Swift 基本排序算法(選擇排序、插入排序、希爾排序)

基本排序

插入排序(Insertion Sort)

  • 時間複雜度(最優):O(n)  當資料的順序正好是由小到大,每回合只需要比較1次。
  • 時間複雜度(最差):Ο(n2) 當資料順序正好是由大到小,每N回合需要比較N次。
  • 時間複雜度(平均):Ο(n2)
  • 空間複雜度:總共O(n)

思路:每次將一個待排序的元素,拿來和已排序的元素進行逐一比較,直到找到合適的位置插入。


希爾排序(Shell Sort)

又稱為「遞減增量排序」,是「插入排序」的優化版。另外,這裡有一個短片,通過跳舞的方式展示Shell Sort是如何運作的。

「插入排序」是不斷的比較鄰近的數字,而「希爾排序」則是先以一定的跨度來進行比較,最後和「插入排序」一樣進行臨近的比較,從而提高效率。


選擇排序(Selection Sort)

  黃色為已排序、紅色為當前最小、藍色為當前位置。

思路:從未排序的元素中找到一個最大(小)的元素放到第一位,接著接著從未排序中找到下一個最大(小)的元素放到已排序的末端,直到排序完成。


推薦&參考

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *