剑指Offer：调整数组顺序使奇数位于偶数前面【21】

题目描述

　　输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题分析

关于排序算法的稳定性

　　排序前后两个相等的数相对位置不变，则算法稳定。

　　具有稳定性的排序算法有：

冒泡排序
归并排序
基数排序
直接插入排序
这般插入排序

　　不稳定性的排序算法有：

堆排序
快速排序
希尔排序
直接选择排序

稳定排序解决问题

　　因为要保证奇数或偶数元素的相对位置不变，很直接就想到的是稳定性排序算法，比较简单的是冒泡和直接插入。使用插入排序法的思想来进行数组整理，不需要额外空间，时间复杂度也很低。

　　我们的整体策略是这样的：设置一个栅栏，栅栏左边的元素是奇数，右边的是偶数，指针从0开始依次向后遍历，如果当前元素是偶数，则后移，是奇数则和栅栏右侧第一个元素交换，栅栏右移一位。

Java题解

package arr;

public class ReOrderArray {
    public static void reOrderArray(int [] array) {

        int brace =-1;
        int ptr =0;
        while (ptr<array.length)
        {
            if(array[ptr]%2==0)
            {
                ptr++;
                continue;
            }
            swap(array,ptr++,++brace);
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {
        int[] arr = {1,3,2,3,4,1,5,6};
        reOrderArray(arr);
        for (int e : arr)
            System.out.println(e);
    }
}