有一个整数数组a,设计一个算法将所有偶数位元素移动到所有奇数位元素的前面,要求它们的相对次序不改变。例如,a={1,2,3,4,5,6,7,8},移动后a={2,4,6,8,1,3, 5,7}。
时间: 2024-10-25 08:11:43 浏览: 25
这个问题可以使用双指针法来解决,通常我们会使用两个指针,一个从数组的第一个元素开始(即奇数位置),另一个从最后一个元素开始(即偶数位置)。然后按以下步骤操作:
1. 初始化两个指针 `left` 和 `right`,分别指向数组的第一个偶数位置和最后一个奇数位置(如果数组长度为奇数,则右边界减一)。
2. 当 `left < right` 时,继续循环:
a. 检查 `a[left]` 是否为偶数。如果是偶数,将其与 `a[right]` 交换位置,然后同时左移 `left` 和右移 `right`。
b. 如果 `a[left]` 是奇数,不做任何交换,直接增加 `left` 的值(向右移动)。
3. 循环结束后,数组就满足条件,所有的偶数位元素都在奇数位元素之前。
Python 代码示例:
```python
def move_even(a):
left = 0
right = len(a) - 1
while left < right:
if a[left] % 2 == 0: # 偶数
a[left], a[right] = a[right], a[left]
right -= 1
else:
left += 1
return a
# 测试
a = [1, 2, 3, 4, 5, 6, 7, 8]
print(move_even(a)) # 输出: [2, 4, 6, 8, 1, 3, 5, 7]
```
阅读全文