java - 如何在没有新数组的情况下对数组进行排序？

Question

我正在做作业，有一道题要求我们对结构数组进行排序

structcitizen 由一个int id 和一个boolean gender 组成，其中id 是随机生成的1 到 100，gender 由 id 是奇数还是偶数决定，odd=true(男性)和 even=false (女)

例如a = {33, true}

题目要求我将citizen[]数组按性别排序，看似很简单，但有如下要求:

run in linear times O(N)

no new array

only constant extra space can be used

我正在考虑使用计数排序，但如果没有新数组似乎有点难以做到，有什么建议吗？

Answer 1

由于这是一道家庭作业题，我不会提供代码。以下内容应该足以让您入门。

这里按性别“排序”实际上是分成两组。通用排序不可能比 O(n*log(n)) 更好，但分区可以在 O(n) 中用常量空间完成。

考虑同时从两端进行迭代(while 循环，两个索引指针初始化为第一个和最后一个元素)寻找“错误”部分中的元素。当你在每一端找到一个这样的元素时，交换它们。请注意，指针彼此独立移动，仅当跳过已在右侧部分的元素时，当然是在交换后立即移动，这是“已在右侧部分的元素”的子情况。

当索引指针在中间某处相遇时退出。

这不是通用排序。对于 key 数量未知的情况，您不能这样做。