我們常用的排序算法，如快排，堆排序等時間復(fù)雜度都為O(nlgn)，這些算法都有一個特點，就是在排序過程中需要進(jìn)行大量的比較，我們稱之為基于比較的排序算法，而這些基于比較的排序算法的時間復(fù)雜度不可能突破O(nlgn)。本文所介紹的算法是基于非比較的排序，其時間復(fù)雜度為線性。

I、計數(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 代碼實現(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)的排序算法