C++ 算法：将整数序列按奇偶排序 (双指针法)

(1) 算法实现：

void sort(int* arr, int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        while (arr[i] % 2 == 0 && i < j) i++; // 从左往右找到第一个奇数
        while (arr[j] % 2 == 1 && i < j) j--; // 从右往左找到第一个偶数
        if (i < j) {
            swap(arr[i], arr[j]); // 交换奇数和偶数
            i++;
            j--;
        }
    }
}

(2) 算法思想：使用双指针法，从序列的两端开始扫描，找到第一个奇数和第一个偶数，然后将它们交换位置，重复这个过程直到两个指针相遇。

(3) 算法注释：

• 使用双指针法，初始时i指向序列的开头，j指向序列的结尾；
• while循环中，先从左往右找到第一个奇数，再从右往左找到第一个偶数；
• 如果i < j，说明还有未扫描的元素，将奇数和偶数交换位置，并将指针向中间移动；
• 重复以上步骤直到两个指针相遇。

(4) 时间复杂度为O(n)，空间复杂度为O(1)。由于只进行一次扫描，并且只使用了常数个额外变量，所以时间和空间复杂度均较低。