数组重排序(如何将所有奇数都放在所有偶数前面)的深入分析_java

这里介绍一种高效的能在O(n)时间复杂度内完成的算法。
核心思想是:定义两个指针,一个指针A从前往后扫描,一个指针B从后往前扫描。指针A扫描到偶数暂停,指针B扫描到奇数暂停,然后交换着两个数,交换之后继续如上述扫描和交换,直到指针A和指针B重合停止。
这个算法的Java代码如下:

复制代码 代码如下:

package Reorder;
public class Reorder {

 public static void main(String[] args) {
  int[] list = { 1, 2, 3, 4, 5, 7, 9, 11 };
  reorderOddEven(list);
 }
 public static void reorderOddEven(int[] list) {
  int length = list.length;
  for (int i = 0; i < length; i++) {
   System.out.print(list[i] + " ");
  }
  System.out.print("\n");
  int begin = 0;
  int end = length - 1;
  while (begin < end) {
   while (begin < end && (list[begin] & 0x1) != 0)
    begin++;
   while (begin < end && (list[end] & 0x1) == 0)
    end--;
   if (begin < end) {
    int temp = list[begin];
    list[begin] = list[end];
    list[end] = temp;
   }
  }
  for (int i = 0; i < length; i++) {
   System.out.print(list[i] + " ");
  }
 }
}

时间: 2016-06-04

数组重排序(如何将所有奇数都放在所有偶数前面)的深入分析_java的相关文章

JS中数组重排序方法_javascript技巧

1.数组中已存在两个可直接用来重排序的方法:reverse()和sort(). reverse()和sort()方法的返回值是经过排序后的数组.reverse()方法会反转数组项的顺序: var values=[1,2,3,4,5]; values.reverse(); alert(values); //5,4,3,2,1 在默认情况下,sort()方法按升序排列数组,sort()方法会调用每个数组项的toString()转型方法,然后比较得到字符串,确定如何排序.即使数组中的每一项都是数值,s

从JVM并发看CPU内存指令重排序(Memory Reordering)

这两天,我拜读了 Dennis Byrne 写的一片博文Memory Barriers and JVM Concurrency (中译文内存屏障与JVM并发). 文中提到: 对主存的一次访问一般花费硬件的数百次时钟周期.处理器通过缓存(caching)能够从数量级上降低内存延迟的成本这些缓存为了性能重新排列待定内存操作的顺序.也就是说,程序的读写操作不一定会按照它要求处理器的顺序执行. 这段话是作者对内存屏障重要性的定义.通过cache降低内存延迟,这句话很好理解.但后面那句"为了性能重排序内存

JVM的重排序

感谢同事[沐剑]的投稿 重排序通常是编译器或运行时环境为了优化程序性能而采取的对指令进行重新排序执行的一种手段.重排序分为两类:编译期重排序和运行期重排序,分别对应编译时和运行时环境. 在并发程序中,程序员会特别关注不同进程或线程之间的数据同步,特别是多个线程同时修改同一变量时,必须采取可靠的同步或其它措施保障数据被正确地修改,这里的一条重要原则是:不要假设指令执行的顺序,你无法预知不同线程之间的指令会以何种顺序执行. 但是在单线程程序中,通常我们容易假设指令是顺序执行的,否则可以想象程序会发生

Javascript数组的排序:sort()方法和reverse()方法

文章简介: JavaScript中的数组排序. JavaScript提供了sort()方法和reverse()方法,使得我们可以简单的对数组进行排序操作和逆序操作.其中: 1.JavaScript的sort()中如果没有指定比较函数,则默认会按照字符的编码顺序进行升序排序.也就是说如果我们想要对数值进行排序得到的不一定是我们想要的结果. 2.Javascript的reverse()将数组中的元素逆序. 先看看上面的第一点,如果有一个数组arr=[1,6,3,7,9],使用arr.sort()后,

深入理解Java内存模型(二) 重排序

如果两个操作访问同一个变量,且这两个操作中有一个为写操作,此时这两个操作之间就存在数据依 赖性.数据依赖分下列三种类型: 上 面三种情况,只要重排序两个操作的执行顺序,程序的执行结果将会被改变. 前面提到过,编译 器和处理器可能会对操作做重排序.编译器和处理器在重排序时,会遵守数据依赖性,编译器和处理器不 会改变存在数据依赖关系的两个操作的执行顺序. 注意,这里所说的数据依赖性仅针对单个处理 器中执行的指令序列和单个线程中执行的操作,不同处理器之间和不同线程之间的数据依赖性不被编译器 和处理器考

Array 重排序方法和操作方法的简单实例

 下面小编就为大家简单的介绍Array中reverse(),sort(),concat(),slice(),splice()方法的应用.一起过来看看吧 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http

Java内存模型FAQ(四)重排序意味着什么?

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html 第四章 译者:Alex 在很多情况下,访问一个程序变量(对象实例字段,类静态字段和数组元素)可能会使用不同的顺序执行,而不是程序语义所指定的顺序执行.编译器能够自由的以优化的名义去改变指令顺序.在特定的环境下,处理器可能会次序颠倒的执行指令.数据可能在寄存器,处理器缓冲区和主内存中以不同的次序移动,而不是按照程序指定的顺序. 例如,如果一个线程写入值到字段a,然后写入

java-eclipse中的debug和指令重排序

问题描述 eclipse中的debug和指令重排序 Java代码经过优化会有指令重排序,那么eclipse的debug按照代码从上到下的顺序执行又是如何做到的 解决方案 debug的程序都是不做优化的,编译的时候使用的是javac -g,除了优化之外,还有assert只在debug的时候才会执行.其实这不是eclipse这样,其他ide也一样 解决方案二: debug按照代码从上到下的顺序执行,是因为debug模式下的代码是未经过优化的. 你不设置断点,debug和Release运行对比一下.

Java内存访问重排序笔记

关于重排序 重排序通常是编译器或运行时环境为了优化程序性能而采取的对指令进行重新排序执行的一种手段. 重排序分为两类:编译期重排序和运行期重排序,分别对应编译时和运行时环境. As-if-serial语义 as-if-serial语义的意思是,所有的动作(Action)都可以为了优化而被重排序,但是必须保证它们重排序后的结果和程序代码本身的应有结果是一致的. Java编译器.运行时和处理器都会保证单线程下的as-if-serial语义. 比如,为了保证这一语义,重排序不会发生在有数据依赖的操作之

php 数组自定义排序:php二维数组自定义排序

<?php//对二维数组自定义排序function array_sort($arr,$keys,$type){$keysvalue=array();$i = 0;foreach($arr as $key=>$val) {$val[$keys] = str_replace("-","",$val[$keys]);$val[$keys] = str_replace(" ","",$val[$keys]);$val[$k