49. Adjust the array so that the odd number is ahead of the even number (129)

  • Topic Description: Input an integer array and implement a function to adjust the order of numbers in the array, so that all odd numbers are in the first half of the array, all even numbers are in the second half of the array, and ensure that the relative positions between odd and odd numbers, even and even numbers remain unchanged.
  • Idea: For arrays, if you don't open up new space, you can only move elements in arrays. For moving elements, we can move odd numbers forward or even numbers backwards. This also guarantees the stability of odd and even numbers. But the average time complexity is O(n^2), which is implemented as follows. The idea of fast queuing can be adopted, and the time complexity is O(nlogn), but this method can not guarantee the stability of odd and even numbers.
  • Code:
package _49.Adjust the array so that the odd number is ahead of the even number;

import java.util.Arrays;

/**
 * Topic Description: Input an integer array and implement a function to adjust the order of numbers in the array so that all odd numbers are in the first half of the array.
 * All even numbers are located in the latter half of the array, and the relative positions between odd and odd numbers, even and even numbers are guaranteed to remain unchanged.
 * @author Administrator
 *
 */
public class ReOrderArray {
	/**
	 * Method 1: Scan the whole array sequentially, place the odd number at the front of the array and move it behind the previous odd number.
	 * @param array
	 */
    public static void reOrderArray1(int [] array) {
    	if(array == null || array.length == 0) return;
        int tmp = 0;
        int k = 0;//Number of odd numbers recorded
        for(int i = 0; i < array.length; i++){
        	//If it is an odd number, move it behind the previous odd number.
        	if(array[i] % 2 == 1){
        		for(int j = i; j > k;j--){
        			tmp = array[j];
        			array[j] = array[j-1];
        			array[j-1] = tmp;
        		}
        		k++;
        	}
        }
    }
    
    /**
     * Method 2: Traverse the array, encounter an even number, move all the elements after the even number forward, and then put the even number in the last position of the array.
     * @param array
     */
    public static void reOrderArray2(int [] array) {
    	if(array == null || array.length == 0) return;
        int tmp = 0;
        int k = 0;//Number of even numbers recorded
        int i = 0;
        while(i < array.length - k){//Even numbers that have been found cannot be traversed again
        	if(array[i] % 2 == 0){
        		tmp = array[i];
        		for(int j = i+1; j < array.length; j++){
        			array[j-1] = array[j];//Move all elements after the even number forward by one position
        		}
        		array[array.length - 1] = tmp;//Then put the even number at the end of the array.
        		k++;
        	}
        	else{
        		i++;
        	}
        }
    }
    
    /**
     * Method 3: This method can not guarantee that the order of the last odd and even numbers is the same as before (unstable).
     * 		Quick row idea: put a pointer before and after the array; for the front pointer, move backward in sequence, and for the back pointer, move forward in sequence.
     * 				The front pointer is always in front of the back pointer. The current pointer traverses to an even number, and the back pointer is exchanged when it traverses to an odd number.
     * @param array
     */
    public static void reOrderArray3(int [] array) {
    	if(array == null || array.length == 0) return;
    	int begin = 0;
    	int end = array.length - 1;
    	while(begin < end){
    		while(array[begin] % 2 == 1 && begin < end)
    			begin++;
    		while(array[end] % 2 == 0 && begin < end)
    			end--;
    		if(begin < end){
    			//Exchange the position of the even number ahead and the odd number behind
        		int sum = array[begin] + array[end];
        		array[begin] = sum - array[begin];
        		array[end] = sum - array[begin];
    		}
    	}
    }
    
    public static void main(String[] args) {
		int[] array = {1,2,3,4,5,6};
		reOrderArray3(array);
		System.out.println(Arrays.toString(array));
	}
}