我們常用的排序算法，如快排赎离，堆排序等時間復(fù)雜度都為O(nlgn)晦攒，這些算法都有一個特點(diǎn)闽撤，就是在排序過程中需要進(jìn)行大量的比較，我們稱之為基于比較的排序算法脯颜，而這些基于比較的排序算法的時間復(fù)雜度不可能突破O(nlgn)哟旗。本文所介紹的算法是基于非比較的排序，其時間復(fù)雜度為線性伐脖。
I热幔、計(jì)數(shù)排序
假設(shè)我們有一個待排序數(shù)組A，其中元素的最小值不小于0讼庇，最大值不超過K绎巨，我們需要建立一個長度為K的線性表C，用來記錄每個元素的個數(shù)蠕啄。這類似于hash的原理场勤。
1.1 算法思路
1、遍歷A歼跟，填充線性表C和媳；
2、遍歷線性表C哈街，依次根據(jù)輸出C[i]個i留瞳；
3、假設(shè)元素個數(shù)為n個骚秦，其中不重復(fù)元素為m個她倘，則時間復(fù)雜度為O(m+n)，空間復(fù)雜度也為O(m+n)作箍；
1.2 代碼實(shí)現(xiàn)
#include <iostream>
#include <vector>
using namespace std;
#define K 100
vector<int> count(K, 0);
void CountingSort(const vector<int>& vec) {
for (int i = 0; i < vec.size(); ++i) {
count[vec[i]]++;
}
}
void myPrint() {
for (int i = 0; i < K; ++i) {
while (count[i]) {
cout << i << " ";
--count[i];
}
}
}
int main() {
vector<int> vec = {0,1,2,3,3,2,5,3,2,2,54,6,23,35,4,2,54,4};
CountingSort(vec);
myPrint();
return 0;
}
II硬梁、此類算法還有桶排序與基數(shù)排序
以后再說明。
歡迎轉(zhuǎn)載胞得，轉(zhuǎn)載請注明出處wenmingxing 時間復(fù)雜度為O(n)的排序算法
