数据结构排序

Question

struct Elem{
int key;
void *data;}
现在有N个不同的数组，其key为0到N-1，要将这N个数组从小到大排序，要求其时间复杂度为o(n)，空间复杂度为o(1)。
大家说说啥思路，要怎么实现呢？
题目确实是这样子的，但仔细看下，这题目很特别，发现没？

Answer 1

既然是o(n)，那意思肯定是要求在线性时间内完成。
问题是：要将这N个数组从小到大排序，是每个数组各自排序还是这N个数组整体排序呢，有点乱。慢慢来。

Answer 2

http://blog.163.com/zhouyii26@126/我的博客里有几个排序算法 希望可以对你有用

Answer 3

你见过时间复杂度是o(n)的排序么？见到了告诉我一声啊。