关于算法-数据结构:一周刷完剑指offer13调整数组顺序使奇数位于偶数前面

调整数组程序使奇数位于偶数后面

1. 题目形容

输出一个整数数组，实现一个函数来调整该数组中数字的程序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半局部，并保障奇数和奇数，偶数和偶数之间的绝对地位不变。

2. 示例

[1, 3, 4, 5, 8, 10]
转变成：
[1, 3, 5, 4, 8, 10]

3. 解题思路

绝对地位不变 —> 放弃稳定性；

奇数位于后面，偶数位于前面 —> 存在判断，移动元素地位；

这些都和外部排序算法类似，思考到具备稳定性的排序算法不多，例如插入排序，归并排序等；这里采纳插入排序的思维实现。

4. Java 实现

public class Solution {public void reOrderArray(int [] array) {
        int index = 0; // 用于保留奇数地位
        int size = array.length;
        
        for (int i =0; i< size; i++){if (array[i] % 2 == 1){ // 如果是奇数的话
                int j = i;
                while (j > index){ // 循环替换奇数和偶数地位，偶数地位绝对不变
                    int temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    j--;
                }
            index++; // 更新奇数地位
                
            }
        }
        
    }
}

5. Python 实现

新建数组空间

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        li1, li2 = [], []
        for ar in array:
            if ar % 2 == 1:
                li1.append(ar)
            else:
                li2.append(ar)
        return li1 + li2 

如果您感觉本文有用，请点个“在看”