剑指Offer 14 *调整数组顺序使奇数位于偶数前面

题目描述

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

思路

1.书上其实没要求调换完之后有序，所以实际上我是两个指针头尾；如果是前指针是偶数，后指针是奇数，就直接调换，可是没想到顺序的问题；
2.如果是排序的话，最简单的的想法是新建一个数组，遍历先把奇数放进去，再放偶数，不过开辟了新的数组
3.如果不想用数组，那就得使用一个神奇的相邻交换了；冒泡其实也是这样的，只不过他的条件是大于或者小于，有n个数，就遍历n个数，然后遍历n次，总会好的；
那么本体中我们要保证的就是偶数不能出现在奇数的前面；

代码

头尾指针未完成版

 static public void reOrderArray(int [] array1) {             //头尾指针
       int array[] =array1;
        int k=0;
        int i = 0;
        int index=array.length-1;
        while (i<index)
        {
            while ((array[index]&1)==0) {
                index--;
                if (index<i)
                    break;
            }
            if ((array[i]&1)==0)
            {
                k=array[i];
                array[i]=array[index];
                array[index]=k;
                index--;
            }
            i++;
//            while (i<index&&(array[i]&1)==1)		//换成while更好一些
//                i++;
//                k=array[i];
//                array[i]=array[index];
//                array[index]=k;
//                index--;
        }
       System.out.println(Arrays.toString(array));
   }

相邻交换

static  public  void  reOrderArray1(int [] array)    //相邻交换
  {
      int k=0;
       for (int i = 0 ; i <array.length-1;i++)
           for (int j = 0 ;j<array.length-1;j++)
           {
               if ((array[j]&1)==0&&(array[j+1]&1)==1)
               {
                   k=array[j];
                   array[j]=array[j+1];
                   array[j+1]=k;
               }
           }
  }

开辟数组的解法

static  public  void  reOrderArray2(int [] array)    //开辟数组
 {
     int test[] = new int[array.length];
     int j = 0;
     for (int i = 0 ; i < array.length; i ++)         //先倒腾奇数
         if ((array[i]&1)==1)
             test[j++]=array[i];
     for (int i = 0 ; i < array.length; i ++)         //在倒腾偶数
         if ((array[i]&1)==0)
             test[j++]=array[i];
      System.arraycopy(test, 0, array, 0, array.length);
     //System.out.println(Arrays.toString(array));
 }

插排

  public  static  void  reOrderArray4(int [] array)
    {
        for ( int i =0 ; i <array.length;i++)
        {   int j ;
            if ((array[i]&1)==1)
            {
                j=i-1;
                int temp=array[i];
                while (j>=0&&(array[j]&1)==0)               //插排中，直到前面没有偶数就停下来
                {                                           //其实也就等于把那些元素全部向后移动了
                    array[j+1]=array[j];
                    j--;
                }
                array[j+1]=temp;
            }
        }
        System.out.println(Arrays.toString(array));
    }
```    
**元素移动**
```java
 public static void reOrderArray3(int[] a) {
        if(a==null||a.length==0)
            return;
        int i = 0,j;
        while(i<a.length){
            while(i<a.length&&!isEven(a[i]))
                i++;
            j = i+1;
            while(j<a.length&&isEven(a[j]))
                j++;
            if(j<a.length){
                int tmp = a[j];
                for (int j2 = j-1; j2 >=i; j2--) {
                    a[j2+1] = a[j2];
                }
                a[i++] = tmp;
            }else{// 查找失敗
                break;
            }
        }
        System.out.println(Arrays.toString(a));
    }
    static boolean isEven(int n){
        if(n%2==0)
            return true;
        return false;
	}

收获

这道题真的是收获很多，首先是思
路上的，有多种思路；
关于冒泡的实践-相邻排序
关于插排的实践
为了保持位置也可以逐个移动

2017-03-22