有一个正整数数组a, 请设计一个高效算法,实现将偶数放在奇数之前。
时间: 2023-06-05 19:47:59 浏览: 126
可以使用双指针法,一个指针指向数组的开头,另一个指针指向数组的末尾。然后,分别从两个方向遍历数组,当左指针指向的数为偶数,右指针指向的数为奇数时,交换两个数的位置。直到左指针和右指针相遇为止,这样就可以将偶数放在奇数之前。
具体实现如下:
1. 定义两个指针i和j,分别指向数组的开头和末尾。
2. 循环遍历数组,当i<j时执行以下操作:
a. 如果a[i]为奇数,i++。
b. 如果a[j]为偶数,j--。
c. 如果a[i]为偶数,a[j]为奇数,交换a[i]和a[j]的值,i++,j--。
3. 循环结束后,数组中的偶数就都放在了奇数之前。
时间复杂度为O(n),空间复杂度为O(1)。
相关问题
一维数组A【0…n-1】中储存了n个正整数,设计算法将数组A中所有的奇数移动到偶数之前,即数组A中左边全是奇数,右边全是偶数。使用c语言
可以使用双指针法来实现将奇数移动到偶数之前的操作。具体实现如下:
```c
void moveOddBeforeEven(int A[], int n) {
int left = 0, right = n - 1;
while (left < right) {
// 从左往右找到第一个偶数
while (left < right && A[left] % 2 == 1) {
left++;
}
// 从右往左找到第一个奇数
while (left < right && A[right] % 2 == 0) {
right--;
}
// 交换左右两个数
if (left < right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
}
}
}
```
代码中,变量`left`表示左边第一个偶数的位置,变量`right`表示右边第一个奇数的位置。双指针分别从左右两端开始移动,找到第一个偶数和第一个奇数,然后交换它们的位置。重复上述步骤,直到左指针和右指针相遇。这样就可以实现将奇数移动到偶数之前的操作。
线性表的应用算法:构造一个递增有序的正整数链表,实现链表分解为一个奇数表和一个偶数表,之后再将两个链表合并一个递减链表。
这个算法的步骤如下:
1. 构造一个递增有序的正整数链表,可以使用插入排序的方法,每次插入一个新的元素时,按照从小到大的顺序插入到链表中。
2. 遍历整个链表,将所有奇数节点放入一个新的链表中,将所有偶数节点放入另一个新的链表中。
3. 将两个链表分别按照从大到小的顺序进行排序,可以使用选择排序或者冒泡排序的方法。
4. 将两个链表合并为一个递减链表,可以使用归并排序的方法,将两个链表按照从大到小的顺序合并为一个新的链表。
最终得到的链表就是一个递减的链表,其中奇数节点和偶数节点分别按照从大到小的顺序排列。