[算法问题]关于数组排序

T720i

如何在时间复杂度O(n),空间复杂度O(1)的情况下对一个长度为100的 int数组排序呢？
想了好几天了

yecheng_110

计数排序

T720i

好象不满足对于复杂度的要求啊！
这是一道笔试题，当时没做出来

wilbur8415

首先   这个数组的元素必须是有一个范围的 才能用计数排序

比如 每个数都是 1-50 范围内的。 每个元素设为a ,排序完成后的数组为b
1）那么就开一个count[50]数组    遍历a数组 如果a= k,
那么count[k]加1
遍历一遍  完成后 cout数组第i个值 存放的是a数组里等于i的元素个数

2）然后从头遍历count数组   令count[j]=count[j-1];
完成后 count数组的第i个值 存放的是a数组里 小于等于i的个数

(3) 再次遍历a数组 比如 a应该放到b数组的哪个位置呢？ 就需要查询count[a]的值 知道a数组里 小于等于a的个数有m个 于是把a放到b[m+1]的位置上去


排序完成

wilbur8415

空间复杂度o(1) 原地排？

Sorehead

谁出的题目呀，骂他没商量。

system888net

原帖由 Sorehead 于 2008-4-16 17:28 发表
谁出的题目呀，骂他没商量。