《剑指Offer》-21.调整数组顺序使奇数位于偶数前面

题干

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

解题思路

O(n^2) 的实现方式

从第一元素开始判断，如果是奇数则继续向后移动，如果是偶数则存入临时变量，然后将数组中该位置后面的所有数字向前移动一位，然后将临时变量的值存入数组的最后一位，以此类推，一致遍历到数组的最后一个元素。

O(n) 的实现方式

维护两个指针p1和p2，分别从数组的开始和结束位置向中间移动，如果p1遇到偶数则移动p2，如果遇到奇数则交换，否则继续移动，直至p2移动到p1之前为止。

代码实现

<?php

function reOrder(array $arr, Closure $compare)
{
    if (empty($arr)) {
        return;
    }
    $start = 0;
    $end = count($arr) - 1;

    while ($start < $end) {
        while ($start < $end && $compare($arr[$start]) == 1) {
            $start++;
        }

        while ($start < $end && $compare($arr[$end]) == 0) {
            $end--;
        }

        if ($start < $end) {
            $tmp = $arr[$start];
            $arr[$start] = $arr[$end];
            $arr[$end] = $tmp;
        }
    }

    return $arr;
}


var_dump(reOrder([1,2,3,4,5,6,7], function($param){
    return $param & 1;
}));