奇偶数排序（调序）

题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，

所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

思路一：从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动O(n)个数字，只是这种方法总的时间复杂度是O(n^２)，不符合要求!

思路二：采用依次遍历数组的方式，从数组的第一个元素开始，判断元素是否是奇数，如果是则将它保存到另一个空数组中，当遍历完整个数组中的奇数时，就将原数组中的所有偶数按照原顺序依次保存到数组的末尾。空间复杂度太大，时间复杂度也不满足要求。

思路三：维护两个指针（头指针和尾指针），一个指针指向数组的第一个数字（头指针），向后移动；一个指针指向最后一个数字（尾指针），向前移动。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。（类似于快速排序）

本方法通过头尾指针往中间扫描，一次遍历完成所有的奇数和偶数的重新排列，时间复杂度是O(n)，符合题目要求。（使用）

思路四：还记得快速排序的过程，设置一个主元，依次遍历元素并使得它和主元进行比较，并按照要去交换元素的位置。

该问题使用两个指针i和j，一个指针指向数组的第一个元素的前一个位置，称为后指针i，向右移动；另一个指针指向数组的第一个元素，称为前指针j，向右移动。前后指针都向后移动的过程中，如果前指针j指向的元素是奇数，则令后指针i向右移动一位，然后交换i和j两个指针所各自指向的元素。我们最终的目的是让奇数排在数组的前面，偶数排在数组的后面，所以i指针指向的是奇数，j指针指向的是偶数。因此，当j指针指向的是奇数时，不正常，让i++，然后交换i，j指针所指向的数。

这种一前一后同时向右扫描的解法，也是一次遍历奇数和偶数的重新排列，时间复杂度是O(n)，符合题目要求。（使用）

总结：虽然思路三和四都实现了，但是它们的输出却有点差别。

//奇偶数排序//思路三
#include using namespace std;//判断是否为奇数
bool IsOddNumber(int data)
{if (data % 2 == 1)//return true;elsereturn false;//return (data & 1) == 1;
}//奇数和偶数的互换
void OddEvenSort(int *pData, unsigned int length)
{if (pData == NULL || length == 0){return;}int *first = pData;int *second = pData + length - 1;while (first < second){//如果头指针指向奇数，正常if (IsOddNumber(*first) == 1){first++;}else if (IsOddNumber(*second) == 0) // 如果尾指针指向偶数，正常{second--;}else//如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字{int temp = *second;*second = *first;*first = temp;}}}int main()
{int a[8] = { 1, 6, 3, 10, 4, 7, 2, 5 };OddEvenSort(a, 8);for (int i = 0; i < 8; i++){cout << a[i] << " ";}cout << endl;return 0;
}
//输出：1 5 3 7 4 10 2 6//思路四
#include using namespace std;//判断是否为奇数
bool IsOddNumber(int data)
{if (data % 2 == 1)//奇数return true;elsereturn false;//return (data & 1) == 1;
}//奇数和偶数互换
void CddEvenSort2(int data[], int low, int high)
{int i = low - 1;for (int j = low; j < high; j++){if (IsOddNumber(data[j]) == 1)//偶数{i++;swap(data[i], data[j]);}}swap(data[i + 1], data[high]);
}
int main()
{int a[8] = { 1, 6, 3, 10, 4, 7, 2, 5 };CddEvenSort2(a, 0, 7);for (int i = 0; i < 8; i++){cout << a[i] << " ";}cout << endl;return 0;
}
//输出：1 3 7 5 4 6 2 10

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！