arrays - 重新排列整数数组

Question

我需要在伪代码和 java 中实现以下内容。

输入:一个整数数组

输出:重新排列数组使其具有以下内容:

1. 假设原数组的第一个元素的值为x
2. 在新数组中，假设x在位置I，即data[I]=x。然后，data[j] <= x for all j x for all j>I。这意味着 x 的“左边”的所有值都小于或等于 x，而“右边”的所有值都大于 x。
3. 示例如下:假设数组的元素初始顺序为:4,3,9,2,7,6,5。应用你的算法后，你应该得到:3,2,4,5,9,7,6。也就是说，最左边的元素 4 在结果数组中的位置使得所有小于 4 的元素(2 和 3)都在它的左边(没有特定的顺序)，所有大于 4 的元素都在它的右边(在没有特别的顺序)。

算法没有空间要求，只需要在O(n)时间内解决问题。

因此，我的印象是冒泡排序在这里最好。

在这种情况下，交换算法不是最佳选择，我想就可以在此处实现的其他方法获得一些反馈。

谢谢!

Answer 1

创建一个包含空间的数组以容纳所有元素。如果 number < x 则将其放在数组的开头，如果 number > x 则将其放在数组的末尾。如果数字等于 x 则忽略它并继续前进。最后，您用等于 x 的值填充剩余的点。