欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer - 12.调整数组顺序使奇数位于偶数前面

程序员文章站 2022-07-10 12:16:52
...

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

知识点:数组

题目:

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

解析:

  • 思路1 : 使用两个for循环迭代,将相邻的偶数和奇数互换位置,类似冒泡排序

  • 思路2: 使用一层for循环保证前i个已经排好顺序,类似插入排序

    题目信息得到: 相对位置不变—>保持稳定性;奇数位于前面,偶数位于后面 —>存在判断,挪动元素位置;

    这些都和内部排序算法相似,考虑到具有稳定性的排序算法不多,例如插入排序,归并排序等;这里采用插入排序的思想实现。

代码:

思路1

    public void reOrderArray(int [] array) {
       for(int i= 0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]%2==0&&array[j+1]%2==1){
                    int t = array[j];
                    array[j]=array[j+1];
                    array[j+1]=t;
                }
            }
        }
    }

思路2

    public void reOrderArray(int [] array) {
        int t = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                int j = i;
                while (j > t) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    j--;
                }
                t++;
            }
        }
    }