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