我们常用的排序算法，如快排，堆排序等时间复杂度都为O(nlgn)，这些算法都有一个特点，就是在排序过程中需要进行大量的比较，我们称之为基于比较的排序算法，而这些基于比较的排序算法的时间复杂度不可能突破O(nlgn)。本文所介绍的算法是基于非比较的排序，其时间复杂度为线性。
I、计数排序
假设我们有一个待排序数组A，其中元素的最小值不小于0，最大值不超过K，我们需要建立一个长度为K的线性表C，用来记录每个元素的个数。这类似于hash的原理。
1.1 算法思路
1、遍历A，填充线性表C；
2、遍历线性表C，依次根据输出C[i]个i；
3、假设元素个数为n个，其中不重复元素为m个，则时间复杂度为O(m+n)，空间复杂度也为O(m+n)；
1.2 代码实现
#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、此类算法还有桶排序与基数排序
以后再说明。
欢迎转载，转载请注明出处wenmingxing 时间复杂度为O(n)的排序算法
