剑指offer代码解析——面试题14调整数组顺序使奇数在偶数之前

本题详细解析都已在代码中注释了:

/**
 * 题目:输入一个数组,要求将奇数放在数组的前半段,偶数放在数组的后半段 
 * @author 大闲人柴毛毛
 */
public class Reorder {
	/**
	 * 分析:本题只要求前半段为奇数,后半段为偶数,没有要求有序,
	 * 因此可以采用快速排序中一趟排序的思想:
	 * 使用两个指针i、j,i指向头、j指向尾,分别向后、向前扫描;
	 * 若i遇到偶数则停下,j遇到奇数则停下,交换这两个数,
	 * 然后继续重复上述操作,直到i、j相遇为止。代码如下:
	 * PS:快速排序算法请看我的博客《剑指 offer——快速排序》
	 */
	public static boolean reorder(int[] a){
		//若数组为空
		if(a==null || a.length==0){
			System.out.println("数组为空!");
			return false;
		}
		
		//若数组只有一个元素,那不做任何操作
		if(a.length==1){
			System.out.println("数组长度为1,无需排序!");
			return true;
		}
		
		//若数组长度超过2,则进行排序
		int i=0,j=a.length-1;
		while(i<j){
			//i从头向后扫描,若当前元素为奇数,则继续往后扫描,若为偶数,i停止扫描。
			while(a[i]%2==1)
				i++;
			//j从后向前扫描,若当前元素为偶数,则继续往前扫描,若为奇数,j停止扫描。
			while(a[j]%2==0)
				j--;
			//当i、j都停止时,如果i和j还没有相遇,就交换这两个数
			if(i<j){
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		return true;
	}
	
	
	/**
	 * 上述代码运行过后会出现死循环!
	 * 当数组全为奇数时,i无限向后寻找,因此出现死循环。
	 * 因此,在i向后、j向前的循环中应多加一个判断:若i搜索到末尾,则停止、若j搜索到开头,则停止。
	 * 修改后的代码如下:
	 */
	public static boolean reorder_modify(int[] a){
		//若数组为空
		if(a==null || a.length==0){
			System.out.println("数组为空!");
			return false;
		}
		
		//若数组只有一个元素,那不做任何操作
		if(a.length==1){
			System.out.println("数组长度为1,无需排序!");
			return true;
		}
		
		//若数组长度超过2,则进行排序
		int i=0,j=a.length-1;
		while(i<j){
			//i从头向后扫描,若当前元素为奇数,则继续往后扫描,若为偶数,i停止扫描。
			while(i<a.length-1 && a[i]%2==1)
				i++;
			//j从后向前扫描,若当前元素为偶数,则继续往前扫描,若为奇数,j停止扫描。
			while(j>0 && a[j]%2==0)
				j--;
			//当i、j都停止时,如果i和j还没有相遇,就交换这两个数
			if(i<j){
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		return true;
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队...

3225
来自专栏Java技术栈

java程序员被误导的一个概念,90%人不知道

我们经常听说List是有序且重复的,Set是无序不重复的。这里有个误区,这里说的顺序有两个概念,一是按添加的顺序排列,二是按自然顺序a-z排列。Set并不是无序...

3176
来自专栏深度学习与计算机视觉

C++ 指针常量与常量指针

吐槽一下: 指针常量与常量指针的翻译就好比机器学习中Regularization翻译成正则化一样,讲真,正则化这个说法确实要比规则化显得高端些,但是到了理解...

1997
来自专栏思考的代码世界

Python编程从入门到实践之条件判断|第4天

在日常开发中需要用到如果怎么样就怎么样,否则就怎么样的逻辑。主要采用if语句来实现的。

3437
来自专栏Golang语言社区

Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法。...

33810
来自专栏Jack的Android之旅

疯狂java笔记之常用的内部排序

在计算机程序开发过程中,经常需要一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快速查找相关记录。

431
来自专栏Python小屋

Python从序列中选择k个不重复元素

集合中的元素不允许重复,Python集合的内部实现为此做了大量相应的优化,判断集合中是否包含某元素时比列表速度快很多。下面的代码用于返回指定范围内一定数量的不重...

3036
来自专栏青青天空树

C语言中把数字转换为字符串 【转】

在将各种类型的数据构造成字符串时,sprintf 的强大功能很少会让你失望。由于sprintf 跟printf 在用法上几乎一样,只是打印的目的地不同而已,前者...

703
来自专栏aCloudDeveloper

右左法则解决复杂声明

Author:bakari       Date: 2012.8.27 现在很多IT公司的面试题都或多或少会有复杂声明的题,有一点C基础的人或许能够瞎搬乱套做对...

2058
来自专栏C/C++基础

C++函数指针简介

(1)定义函数指针的语法形式比较复杂,常借助于typedef类型定义符来简化函数指针的定义。

301

扫描关注云+社区