调整数组顺序使奇数位于偶数前面

一、问题描述

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

二、算法思路

这是一个插入排序的变种，实际上比插入排序更加简单。

插入排序的主要任务是维护一个部分有序的数组，插入使得有序部分不断扩大。而这里的主要任务可以看作是维护一个（不改变顺序的）奇数数组，因为只要不两两交换，那么偶数的先后顺序是不会变动的，所以等排好了奇数部分，偶数部分自然也就大功告成了。

三、算法实现

3.1、Java实现版

public class Solution {    public void reOrderArray(int [] array) {        int i=-1;//i表示奇数序列最后一个元素的下标        for(int k=0;k
    
     i+1){                    array[k]=array[k-1];                    k--;                }                array[i+1]=temp;                i++;            }        }    }}
    

解释：代码中的i表示的是奇数序列最后一个元素的下标。当找到新的奇数时，先将这个奇数保存，把从它往左的到第一个偶数整体往右移动一个单位，并在i+1的地方放上之前保存的奇数，到此，一趟循环已经完成。如果是偶数的话，直接跳过。