我正在做我的作业,并且有一个问题要求我们对结构数组进行排序
结构citizen由a int id和a组成boolean gender,其中id随机生成1到100之间,gender由if id是奇数还是偶数,奇数= true(男性)和偶数= false(女性)确定
例如 a = {33, true}
这个问题要求我citizen[]按性别对数组进行排序,看起来很容易,但它有以下要求:
以线性时间运行O(N)
没有新阵列
只能使用恒定的额外空间
我正在考虑使用计数排序但是如果没有新阵列似乎有点困难,有什么建议吗？
由于这是一个家庭作业问题,我不打算提供代码.以下内容足以让您入门.
按性别"排序"实际上意味着分成两组.通用排序不能比O(n*log(n))更好,但是可以在具有恒定空间的O(n)中进行分区.
考虑同时从两端迭代(while循环,两个索引指针初始化为first和last元素),寻找"错误"部分中的元素.当你在每一端找到一个这样的元素时,交换它们.请注意,指针只在跳过已经在右边部分的元素时才会相互独立移动,当然也可以在交换后立即移动,这是"已经在右边部分中的元素"的子例.
当索引指针在中间某处相遇时退出.
这不是一般目的.如果密钥数量未知,则无法执行此操作.
| 归档时间： |
|
| 查看次数： |
114 次 |
| 最近记录： |