剑指offer JS题解 (13)调整数组顺序使奇数位于偶数前面数据结构与算法华工Web练习生-

题目描述

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

解题思路

之前我是在leetcode上面做的这道题，leetcode上没有保证奇数和奇数，偶数和偶数之间的相对位置不变这个限制条件，做起来相对自由，可以用头尾双指针（对撞）交换的方式去做。但这道题在牛客上增加了这个条件，难度就上来了。

解法一，我一开始做的思路是把奇数与偶数分开来，然后再合并。相当于遍历第一次划分奇数偶数，遍历第二次合并两数组，遍历两次，所以：
时间复杂度为O（2n）=O（n），缺点是需要开辟额外的空间，空间复杂度为O（n）。

解法二是模仿插入排序的过程，举个例子：
现在输入的数组是5,6,8,9,7,2,1，我们要做的其实就是把偶数向右移，奇数向左移。但是这两组数同时移动的话会比较困难，我们可以分解成一组数和单个数做多次移动（就像插入排序一样）。
我们可以用一个头指针去指向最左边的偶数，这里是6，再用一个跟随指针去寻找离头指针最近的右边的奇数，这里是9。现在要把6以及它之后跟随的偶数集体右移，然后原先6所在的位置空出来了，把这个位置给9，就做到了偶数组的局部右移，单个奇数左移，整体上没有改变奇数组和偶数组各自内部的相对位置。之后就是寻找下一个偶数，循环进行这个过程。

现在用这个思路去整理伪代码：
1、头指针向右移动，直到遇到偶数，接着开启新循环，寻找头指针右边最近的奇数，找到则用跟随指针指向其下标，用临时变量记录奇数的值；如果没能找到奇数，判断数组越界，结束程序。
2、使 [头指针，跟随指针）这个区间的偶数整体右移，再向原先头指针指向的位置插入临时变量中的奇数；
3、头指针继续右移，寻找下一个偶数，找到则重复1、2过程；如果没有寻找到偶数，判断数组越界，结束程序。

这种解法的时间复杂度是O（n^2），由于是在原数组上进行移动，空间复杂度为O（1）。

Code

//解法一，开辟额外空间 function reOrderArray(array) { // write code here const arr = []; // 奇数数组 const brr = []; // 偶数数组     array.forEach(item => {         item % 2 ? arr.push(item) : brr.push(item); }); return arr.concat(brr); } //解法二，模仿插入排序 function reOrderArray(array) { // write code here let i=0; let j=0; while(i<array.length){ for(;i<array.length;i++){ if(!(array[i]&1)){ break; } } if(i==array.length){ return array; }else{ let temp; for(j=i+1;j<array.length;j++){ if(array[j]&1){                     temp=array[j]; break; } } if(j==array.length){ return array; }else{ for(let k=j;k>i;k--){                     array[k]=array[k-1]; }                 array[i]=temp; } } } return array; } 

运行环境：JavaScript (V8 6.0.0)
运行时间：13ms
占用内存：5348k