검지 Offer - 문제 14: 배열 순 서 를 조정 하여 홀수 가 짝수 앞 에 있 도록 합 니 다.

1. 기초 판:
질문 설명:
하나의 정수 배열 을 입력 하여 하나의 함 수 를 실현 하여 이 배열 의 숫자의 순 서 를 조정 하여 모든 홀수 가 배열 의 앞부분 에 있 고 모든 짝수 는 배열 의 후반 부분 에 있 습 니 다.
문제 분석:
두 손가락 침 법 사용 고려 하기;
방법 1: 두 개의 포인터 p1, p2 를 유지 하고 각각 배열 의 머리 와 꼬리 부터 중간 으로 갑 니 다.p1 이 홀수 일 때 p1 은 계속 앞으로 갑 니 다.p2 가 짝수 일 때 p2 도 계속 가운데 로 갑 니 다.p1 이 짝수 를 가리 키 고 p2 가 홀수 를 가리 킬 때 두 값 을 교환 합 니 다.
방법 2: 빠 른 정렬 의 알고리즘 을 참고 하여 두 개의 포인터 p1, p2 를 유지 합 니 다.두 바늘 모두 처음부터 앞으로 갑 니 다. p2 는 계속 앞으로 옮 겨 다 닙 니 다. p2 가 짝수 일 때 p1 은 정체 되 어 있 습 니 다.p2 가 홀수 일 때 p2 와 p1 이 있 는 값 을 교환 하고 p1 을 한 걸음 앞으로 이동 합 니 다.
코드:
방법 1:

public class Solution {
    public void reOrderArray(int [] array) {
        if (array == null || array.length <= 1)
            return;
        //     
        int start = 0;
        int end = array.length - 1;

        while (start <= end) {
            if ((array[start] & 0x1) == 1)
                start++;
            if ((array[end] & 0x1) == 0)
                end--;

            if (((array[start] & 0x1) == 0)&&((array[end] & 0x1) == 1)) {
                int temp = array[start];
                array[start] = array[end];
                array[end] = temp;
            }
        }

    }
}

방법 2:

public class Solution {
    public void reOrderArray(int [] array) {
        if (array == null || array.length <= 1)
            return;
        int index = 0;

        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 0x1) == 1) {
                int temp = array[i];
                array[i] = array[index];
                array[index] = temp;
                index ++;
            }

        }
    }
}

2. 향상 판:
질문 설명:
    하나의 정수 배열 을 입력 하여 하나의 함 수 를 실현 하여 이 배열 의 숫자의 순 서 를 조정 하여 모든 홀수 가 배열 의 앞부분 에 있 고 모든 짝수 가 배열 의 후반 부분 에 있 으 며 홀수 와 홀수, 짝수 와 짝수 간 의 상대 적 인 위치 가 변 하지 않도록 합 니 다.
문제 분석:
앞의 방법 은 교환 을 사용 하여 배열 의 짝수 와 짝수, 홀수 와 홀수 사이 의 원래 순 서 를 파괴 했다.여 기 는 거품 정렬 과 유사 한 방법 으로 매번 순환 할 때마다 짝수 치 를 맨 아래로 가 라 앉 히 거나 홀수 치 를 맨 위로 올 립 니 다.시간 복잡 도 O (n ^ 2)
    또는 공간 을 사용 하여 시간 을 바 꾸 는 방법 으로 하나의 배열 을 열 어 기이 한 수치 나 짝수 치 를 저장 하고 앞의 방법 2 와 결합 하여 조작 하 며 공간 복잡 도 는 O (n) 이 고 시간 복잡 도 는 O (n) 이다.
코드:

public class Solution {
    public void reOrderArray(int [] array) {
        if (array == null || array.length <= 1)
            return;
        int index = 0;
        //        ，        
        for (int i = array.length - 1; i >= 0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (((array[j] & 0x1) == 0)&&((array[j + 1] & 0x1) == 1)) {
                    swap(array, j, j + 1);
                }
            }
        }
    }

    private void swap (int[] data, int i , int j) {
        int temp = data[i];
        data[i]  = data[j];
        data[j]  = temp;
    }
}