排序 sorting

排序(sorting)

將一組資料一使用者需求，予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料，優點為容易閱讀、統計分析、與快速搜尋所要之資料。

「資料結構」課程中，排序法分分類方式有三類：

第一類：內部與外部排序

內部排序(Internal sort)又稱「陣列排序」

  【定義】排序之工作，主要在主記憶體(RAM)完成

  【適用時機】資料量較少者;

外部排序(External sort)又稱「檔案排序」

  【定義】排序之工作，主要是在輔助記憶體(Disk, File)完成

  【適用時機】資料量較大者

第二類：穩定與不穩定排序法

穩定排序法(stable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前相同時，稱穩定排序

  【例如】

  排序前：3,5,19,1,3*,10

  排序後：1,3,3*,5,10,19 (因為兩個3, 3*的相對位置在排序前與後皆相同。)

不穩定排序法(unstable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前不相同時，稱不穩定排序。

  【例如】

  排序前：3,5,19,1,3*,10

  排序後：1,3*,3,5,10,19 (因為兩個3, 3*的相對位置在排序前與後不相同。)

第三類：簡單與高等排序法

簡單排序法

  【定義】排序演算法簡單，但執行時間較長

  【平均時間複雜度】

高等排序法

  【定義】排序演算法複雜，執行時間較短

  【平均時間複雜度】