|
排序(Sorting) 將一組資料，予以重新排列，使其由大至小或由小至大的順序排列。排序後之資料，在爾後的處理上，無論是搜尋、統計分析...都可提高處理效率，在本教學網的單元 6 之陣列作業上，第 8 至 11 題，就是很好的範例，讀者可以試著將資料已排序的條件去除，並回答 8 至 11 題的問題，就可知道排序後對於爾後處理資料的效率提升有多大幫助。 下列針對排序相關專有名詞做一解釋 內部排序 內部排序(Internal sort)又稱「陣列排序」。 【定義】排序之工作，主要在主記憶體(RAM)完成。 【適用時機】資料量較少者。 外部排序 外部排序(External sort)又稱「檔案排序」。 【定義】排序之工作，主要是在輔助記憶體(Disk, File)完成。 【適用時機】資料量較大者。 穩定排序 穩定排序法(stable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前相同時，稱穩定排序。 【例如】 排序前：4,6,13,1,4,12 排序後：1,4,4,6,12,13 (因為兩個 4, 4 的相對位置在排序前與後皆相同。) 不穩定排序 不穩定排序法(unstable sorting)，如果鍵值相同之資料，在排序後相對位置與排序前不相同時，稱不穩定排序。 【例如】 排序前：4,6,13,1,4,12 排序後：1,4,4,6,12,13 (因為兩個 4, 4 的相對位置在排序前與後不相同。) 簡單排序法 【定義】排序演算法簡單，但執行時間較長。 進階排序法 進階排序法 【定義】排序演算法複雜，執行時間較短。 時間複雜度 【定義】演算法在電腦執行時，所需消耗的時間，以 big O 表示。 (註：此時間並非秒或分、時，而是電腦執行指令的數量) 【例如】 for(i=0; i<n; i++) s+=a; 上面程式的時間複雜度為 O(n) 【例如】 for(i=0; i<n; i++) for(j=0; j<n; j++) s+=a; 上面程式的時間複雜度為 O(n2) 空間複雜度 【定義】電腦完全地執行演算法所需的記憶體量。 (註：所需的記憶體量，大概可以看成所用的變數量。) 常見之排序演算法
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||