【题21 调整数组顺序使奇数位于偶数前面】

你的名字 2022-03-26 11:24 126阅读 0赞

**【题21调整数组顺序使奇数位于偶数前面】**  
**【题目】**  
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

**法一：不考虑时间复杂度**  
从头扫描数组，碰到偶数，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位，挪动完之后在数组的末尾有一个空位，偶数放进去。没碰到一个，移动O（n）个数字，总的时间复杂度O（n^2）

**法二：扫描数组，如果发现偶数在奇数前，交换顺序。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**法三：考虑扩展解法**  
问：如果题目改成把数组中的数按大小分为2部分，负数放在非负数前面？  
按被3整除，能被整除的放在不能被整除的前面？  
希望给出一种模式，在这种模式下能够很方便地把已有方案**扩展**到同类型去**修改2处判断标准**，判断标准变成一个函数指针。即用一个单独的函数来判断数字是不是符合标准  
**函数解耦成两部分**  
（1） 判断数字应该在数组前半部分还是后半部分  
（2） 拆分数组的操作。

**实现**

package ti21;
    
    public class Solution {
    	//实现代码 方法一
    	public void reorderOddEven(int []number){
    		if(number == null && number.length == 0){
    			return;
    		}
    		int len = number.length; //存储数组长度
    		int count = 0; //控制数组遍历的循环次数
    		for (int i = 0; i < len && count < len; ++i) { //
    			++count;
    			int temp = number[i];
    			if((temp & 0x1) == 0){ //注释1
    			//如果为偶数，移动数组，将数放入数组末尾，并使i在i-1的位置，重新开始判断
    				for (int j = i; j < len-1; ++j) {
    					number[j] = number[j+1];
    				}
    				number[len-1] = temp;
    				--i;
    			}
    		}
    	}
    	
    	//法一的优化代码
    	public void reorderOddEven2(int []number){
    		if(number == null && number.length == 0){
    			return;
    		}
    		for (int i = 0, j = 0; i < number.length; ++i) {
    			if((number[i] & 0x1) != 0){
    				int temp = number[i];
    				number[i] = number[j];
    				number[j] = temp;
    				++j;
    			}
    		}
    	}
    	
    	//交换奇偶数
    	public void reorderOddEven1(int []number){
    		int len = number.length;
    		if(number == null || len == 0){
    			return;
    		}
    		int begin = 0;
    		int end = len -1;
    		while(begin < end){
    			while((begin < end) && (number[begin] & 0x1) != 0){
    				++begin;
    			}
    			while((begin < end) && (number[end] & 0x1) == 0){
    				--end;
    			}
    			if(begin < end){
    				int temp = number[begin];
    				number[begin] = number[end];
    				number[end] = temp;
    			}
    		}
    	}
    	
    	//扩展
    	public void order(int[] arr){
    		if(arr == null)
    			return;
    		int i = 0;
    		int j = arr.length-1;
    		while(i<j){
    			if(isEven(arr[i]) && !isEven(arr[j])){
    				int temp = arr[i];
    				arr[i]= arr[j];
    				arr[j] = temp;
    			}
    			else if(!isEven(arr[i]) && isEven(arr[j])){
    				i++;
    			}
    			else if(isEven(arr[i]) && isEven(arr[j])){
    				j--;
    			}else{
    				i++;
    				j--;
    			}
    		}
    	}
    	public boolean isEven(int n){
    		return (n & 1) == 0;
    	}
    	
    	public static void main(String[] args){
    		Solution test = new Solution();
    		int[] arr= {1,2,3,4,5,6,12,7,8,9,10};
    		test.reorderOddEven(arr);
    		for(int i = 0;i<arr.length ;i++){
    			System.out.print(arr[i]+",");
    		}
    		System.out.println();
    		System.out.println("*******************");
    		
    		int[] arr1= {1,2,3,4,5,6,12,7,8,9,10};
    		test.reorderOddEven2(arr1);
    		for(int i = 0;i<arr1.length ;i++){
    			System.out.print(arr[i]+",");
    		}
    		System.out.println();
    		System.out.println("*******************");
    		
    		int[] arr2= {1,2,3,4,5,6,12,7,8,9,10};
    		test.reorderOddEven1(arr2);
    		for(int i = 0;i<arr2.length ;i++){
    			System.out.print(arr2[i]+",");
    		}
    		System.out.println();
    		System.out.println("*******************");
    		
    		int[] arr3= {1,2,3,4,5,6,12,7,8,9,10};
    		test.order(arr3);
    		for(int i = 0;i<arr3.length ;i++){
    			System.out.print(arr3[i]+",");
    		}
    		System.out.println();
    		System.out.println("*******************");
    	}
    }

**运行结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]

**注释1**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]

参考：  
1.《剑指offer》2.[https://blog.csdn.net/jsqfengbao/article/details/47185277][https_blog.csdn.net_jsqfengbao_article_details_47185277]  
3.[https://blog.csdn.net/u013132035/article/details/80580602][https_blog.csdn.net_u013132035_article_details_80580602]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220326/eb28ef7cba434e63b2c032a8ad90ba8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220326/cb6f98f3f17e420f9f9b3d99d592b8c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20220326/5108948609b747c9a846f1d435b3a54c.png
[https_blog.csdn.net_jsqfengbao_article_details_47185277]: https://blog.csdn.net/jsqfengbao/article/details/47185277
[https_blog.csdn.net_u013132035_article_details_80580602]: https://blog.csdn.net/u013132035/article/details/80580602