摘要: 排序是數據處理中經常使用的一種重要運算，在計算機及其應用系統中，花費在排序上的時間在系統運行時間中占有很大比重，其重要性無需多言。下文將介紹常用的如下排序方法，對它們進行簡單的分析和比較，并提供 C/C++ 語言實現。
所謂排序，就是要將一堆記錄，使之按關鍵字遞增(或遞減)次序排列起來。根據排序所采用的策略，可以分為如上五種：
1、插入排序（直接插入排序、希爾排序）；
2、交換排序（冒泡排序、快速排序）；
3、選擇排序（直接選擇排序、堆排序）；
4、歸并排序；
5、桶排序（桶排序，基數排序）；
其中插入排序、交換排序、選擇排序、選擇排序、歸并排序都是基于關鍵字比較的排序，比較排序的平均時間復雜度好不過 O(nlogn)。
而桶排序是基于映射的排序，其平均時間復雜度可達到 O(n)，但桶排序需要額外的空間來存儲經過映射的記錄。
通常在待排序記錄較多的時候，基于映射的排序 O(n) 比基于比較的排序 O(nlogn) 的效率要高得多，這很好理解：用空間換時間。（查找算法其實也是如
閱讀全文