数据结构――算法之（017）（如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)）

【申明：本文仅限于自我归纳总结和相互交流，有纰漏还望各位指出。联系邮箱：Mr_chenping@163.com】

题目：

如何对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

数据结构――算法之（017）（ 如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)）