數據結構——算法之（017）（ 如何對n個數進行排序，要求時間復雜度O(n)，空間復雜度O(1)）

【申明：本文僅限於自我歸納總結和相互交流，有纰漏還望各位指出。 聯系郵箱：[email protected]】

題目：

如何對n個數進行排序，要求時間復雜度O(n)，空間復雜度O(1)

題目分析：

一、乍一看，不可能完成。時間復雜度為n，縱觀所有的排序法，沒有達到這個級別的

二、如果針對的是有限個數排列，可以采用標記法，或者說它是一種hash思想的方法，申請一個大大的數組hash[65536]

然後對相應的位置標記一下，重復的數字則疊加

例如：

0----->hash[0]++;

5----->hash[5]++;

100--->hash[100]++;

算法實現：

#include 

static int hash[65536] = {0};
void hash_sort(int *array, int size)
{
    int i=0;
    for(; i