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

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

题目描述

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

解题思路

运用插入思想

1. 要想让相对位置不变，则需要相邻位置交换
2. 引入标志位k 表示前半部分最后一个奇数位置
3. 寻找到下一个奇数时，将标志位 k 之后到当前奇数位置上的数按照顺序从后向前相邻移动奇数到k位置

代码实现

java 代码

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

    public static void main(String[] args){
        int[] arr = {4,1, 3, 2, 5, 7, 4, 6, 9, 8, 3};
        reOrderArray(arr);
        System.out.println(Arrays.toString(arr));
    }

Kotlin 代码

    /**
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
     * 运用插入思想
     * 1. 要想让相对位置不变，则需要相邻位置交换
     * 2. 引入标志位k 表示前半部分最后一个奇数位置
     * 3. 寻找到下一个奇数时，将标志位 k 之后到当前奇数位置上的数按照顺序从后向前相邻移动奇数到k位置
     * @param array
     */
    fun reOrderArray(array: IntArray) {
        var k = 0
        for (i in array.indices) {
            if (array[i] % 2 != 0) {
                for (j in i downTo k + 1) {
                    val temp = array[j - 1]
                    array[j - 1] = array[j]
                    array[j] = temp
                }
                k++
            }
        }
    }


    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val arr = intArrayOf(4, 1, 3, 2, 5, 7, 4, 6, 9, 8, 3)
        reOrderArray(arr)
        println(arr.contentToString())
    }

引用声明

该题目引用自
牛客网