📃 题目描述

题目链接：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 (opens new window)

🔔 解题思路

双指针（不稳定）

和 283. 移动零 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 一样，left 指针指向偶数，right 用来找奇数，然后将两个指针指向的元素进行交换就可以，这种方法没法保证原始顺序，是一种不稳定的算法

class Solution {
    public int[] exchange(int[] nums) {
        int left = 0;
        int right = left + 1;
        while (left < nums.length) {
            // 当前数是偶数，向后找到第一个奇数与其交换
            if (nums[left] % 2 == 0) {
                right = left + 1;
                for (; right < nums.length; right ++) {
                    if (nums[right] % 2 != 0) {
                        swap(nums, left, right);
                        break;
                    }
                }
            }

            left ++;
        }

        return nums;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

冒泡（稳定）

类似于冒泡排序的思想，从后往前两两比较，如果发现偶数在前而奇数在后，则进行交换，就是相当于把奇数不断的冒泡到数组的前面

稳定的算法，但是时间复杂度 O(N^2)，LC 上这道题会超时

秋招做天翼云笔试的时候有这个原题，要求保证相对顺序，这样做能 AC

class Solution {
    public int[] exchange(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i ++) {
            for (int j = n - 1; j > 0; j --) {
                int pre = nums[j - 1];
                int post = nums[j];
                // 偶数在前，奇数在后，则进行交换
                if (pre % 2 == 0 && post % 2 != 0) {
                    swap(nums, j - 1, j);
                }
            }
        }

        return nums;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}