簡介
挑選排序法時會希望比較、交換、配置空間等操作的次數越少越好，然而世上沒有完美的排序法，必須在比較、交換、配置空間中做出取捨．
比較次數很多，交換次數少，無需額外配置空間的排序算法
選擇排序法（Selection Sort）是一個典型的例子。在選擇排序中，算法會遍歷陣列多次。每次遍歷時，它都會尋找剩餘未排序部分的最小（或最大）元素，然後將其與未排序部分的第一個元素交換。因此，儘管比較次數很多（幾乎是O(n^2)），但交換的次數相對較少，最多只有n-1次交換。
比較次數少，交換次數少，無需額外配置空間的排序算法
冒泡排序（Bubble Sort）在某種程度上滿足這一條件。它通過重複遍歷要排序的陣列，每次遍歷時比較相鄰的元素，如果它們的順序錯誤就把它們交換過來。冒泡排序的比較次數可以接近選擇排序，但每次比較錯誤時就會進行交換，因此在最壞的情況下（陣列完全逆序），它可能會進行大量的交換操作。
比較次數少，交換次數少，無需額外配置空間的排序算法
歸併排序（Merge Sort）是這一類別的代表。歸併排序在最好、最壞和平均情況下的時間複雜度都是O(n log n)，比較和交換（實際上是陣列元素的複製）的次數相對較少。然而，它需要額外的空間來臨時存儲那些被合併的元素，空間複雜度為O(n)，這意味著它需要大量的配置空間。
各項操作所花費時間分析
透過一個簡單的實驗來量測比較、交換、配置空間的執行時間，實際的運行結果會因prefetch, cache hit/miss, compiler optimization, malloc implementation 有很大的關係，跟以下的測試會有一定程度的差異，但總體而言交換跟配置空間所花費的時間一定比比較還要高．
當排序的時間 >> 配置空間的時間，通常會傾向使配置大量空間來減少排序時間的演算法．
實驗環境:
電腦: M2 Air,
編譯器: gcc -O0
配置空間: 10000個整數單元的陣列
單次動作量測
寫入操作總耗時：4 clocks
讀取操作總耗時：2 clocks
比較操作總耗時：0.5 clocks
動態記憶體分配操作總耗時：20 clocks