并行基排序java代码 适合并行处理的排序

java并发常识

1.java并发编程是什么

深泽网站建设公司成都创新互联公司,深泽网站设计制作，有大型网站制作公司丰富经验。已为深泽上千多家提供企业网站建设服务。企业网站搭建\成都外贸网站建设要多少钱，请找那个售后服务好的深泽做网站的公司定做！

1， 保证线程安全的三种方法： a， 不要跨线程访问共享变量b， 使共享变量是final类型的c， 将共享变量的操作加上同步 2， 一开始就将类设计成线程安全的， 比在后期重新修复它，更容易。

3， 编写多线程程序， 首先保证它是正确的， 其次再考虑性能。 4， 无状态或只读对象永远是线程安全的。

5， 不要将一个共享变量 *** 在多线程环境下（无同步或不可变性保护） 6， 多线程环境下的延迟加载需要同步的保护， 因为延迟加载会造成对象重复实例化 7， 对于volatile声明的数值类型变量进行运算， 往往是不安全的（volatile只能保证可见性，不能保证原子性）。 详见volatile原理与技巧中， 脏数据问题讨论。

8， 当一个线程请求获得它自己占有的锁时（同一把锁的嵌套使用）， 我们称该锁为可重入锁。在jdk1。

5并发包中， 提供了可重入锁的java实现-ReentrantLock。 9， 每个共享变量，都应该由一个唯一确定的锁保护。

创建与变量相同数目的ReentrantLock， 使他们负责每个变量的线程安全。 10，虽然缩小同步块的范围， 可以提升系统性能。

但在保证原子性的情况下， 不可将原子操作分解成多个synchronized块。 11， 在没有同步的情况下， 编译器与处理器运行时的指令执行顺序可能完全出乎意料。

原因是， 编译器或处理器为了优化自身执行效率， 而对指令进行了的重排序（reordering）。 12， 当一个线程在没有同步的情况下读取变量， 它可能会得到一个过期值， 但是至少它可以看到那个线程在当时设定的一个真实数值。

而不是凭空而来的值。 这种安全保证， 称之为最低限的安全性（out-of-thin-air safety） 在开发并发应用程序时， 有时为了大幅度提高系统的吞吐量与性能， 会采用这种无保障的做法。

但是针对， 数值的运算， 仍旧是被否决的。 13, volatile变量，只能保证可见性， 无法保证原子性。

14， 某些耗时较长的网络操作或IO， 确保执行时， 不要占有锁。 15， 发布（publish）对象， 指的是使它能够被当前范围之外的代码所使用。

（引用传递）对象逸出（escape）， 指的是一个对象在尚未准备好时将它发布。 原则： 为防止逸出， 对象必须要被完全构造完后， 才可以被发布（最好的解决方式是采用同步） this关键字引用对象逸出 例子： 在构造函数中， 开启线程， 并将自身对象this传入线程， 造成引用传递。

而此时， 构造函数尚未执行完， 就会发生对象逸出了。 16， 必要时， 使用ThreadLocal变量确保线程封闭性（封闭线程往往是比较安全的， 但一定程度上会造成性能损耗）封闭对象的例子在实际使用过程中， 比较常见， 例如 hibernate openSessionInView机制， jdbc的connection机制。

17， 单一不可变对象往往是线程安全的（复杂不可变对象需要保证其内部成员变量也是不可变的）良好的多线程编程习惯是： 将所有的域都声明为final， 除非它们是可变的。

2.Java线程并发协作是什么

线程发生死锁可能性很小，即使看似可能发生死锁的代码，在运行时发生死锁的可能性也是小之又小。

发生死锁的原因一般是两个对象的锁相互等待造成的。 在《Java线程：线程的同步与锁》一文中，简述死锁的概念与简单例子，但是所给的例子是不完整的，这里给出一个完整的例子。

/** * Java线程：并发协作-死锁 * * @author Administrator 2009-11-4 22:06:13 */ public class Test { public static void main(String[] args) { DeadlockRisk dead = new DeadlockRisk(); MyThread t1 = new MyThread(dead, 1, 2); MyThread t2 = new MyThread(dead, 3, 4); MyThread t3 = new MyThread(dead, 5, 6); MyThread t4 = new MyThread(dead, 7, 8); t1。 start(); t2。

start(); t3。start(); t4。

start(); } } class MyThread extends Thread { private DeadlockRisk dead; private int a, b; MyThread(DeadlockRisk dead, int a, int b) { this。 dead = dead; this。

a = a; this。b = b; } @Override public void run() { dead。

read(); dead。write(a, b); } } class DeadlockRisk { private static class Resource { public int value; }。

3.如何学习Java高并发

1.学习 *** 并发框架的使用，如ConcurrentHashMAP,CopyOnWriteArrayList/Set等2.几种并发锁的使用以及线程同步与互斥，如ReentainLock,synchronized,Lock,CountDownLatch,Semaphore等3.线程池如Executors,ThreadPoolExecutor等4.Runable,Callable,RescureTask,Future,FutureTask等5.Fork-Join框架以上基本包含完了，如有缺漏请原谅。

4.并发编程的Java抽象有哪些呢

一、机器和OS级别抽象 （1）冯诺伊曼模型 经典的顺序化计算模型，貌似可以保证顺序化一致性，但是没有哪个现代的多处理架构会提供顺序一致性，冯氏模型只是现代多处理器行为的模糊近似。

这个计算模型，指令或者命令列表改变内存变量直接契合命令编程泛型，它以显式的算法为中心，这和声明式编程泛型有区别。 就并发编程来说，会显著的引入时间概念和状态依赖 所以所谓的函数式编程可以解决其中的部分问题。

（2）进程和线程 进程抽象运行的程序，是操作系统资源分配的基本单位，是资源cpu，内存，IO的综合抽象。 线程是进程控制流的多重分支，它存在于进程里，是操作系统调度的基本单位，线程之间同步或者异步执行，共享进程的内存地址空间。

（3）并发与并行 并发，英文单词是concurrent，是指逻辑上同时发生，有人做过比喻，要完成吃完三个馒头的任务，一个人可以这个馒头咬一口，那个馒头咬一口，这样交替进行，最后吃完三个馒头，这就是并发，因为在三个馒头上同时发生了吃的行为，如果只是吃完一个接着吃另一个，这就不是并发了，是排队，三个馒头如果分给三个人吃，这样的任务完成形式叫并行，英文单词是parallel。 回到计算机概念，并发应该是单CPU时代或者单核时代的说法，这个时候CPU要同时完成多任务，只能用时间片轮转，在逻辑上同时发生，但在物理上是串行的。

现在大多数计算机都是多核或者多CPU，那么现在的多任务执行方式就是物理上并行的。 为了从物理上支持并发编程，CPU提供了相应的特殊指令，比如原子化的读改写，比较并交换。

（4）平台内存模型 在可共享内存的多处理器体系结构中，每个处理器都有它自己的缓存，并且周期性的与主存同步，为什么呢？因为处理器通过降低一致性来换取性能，这和CAP原理通过降低一致性来获取伸缩性有点类似，所以大量的数据在CPU的寄存器中被计算，另外CPU和编译器为了性能还会乱序执行，但是CPU会提供存储关卡指令来保证存储的同步，各种平台的内存模型或者同步指令可能不同，所以这里必须介入对内存模型的抽象，JMM就是其中之一。 二、编程模型抽象 （1）基于线程模型 （2）基于Actor模型 （3）基于STM软件事务内存 …… Java体系是一个基于线程模型的本质编程平台，所以我们主要讨论线程模型。

三、并发单元抽象 大多数并发应用程序都是围绕执行任务进行管理的，任务是抽象，离散的工作单元，所以编写并发程序，首要工作就是提取和分解并行任务。 一旦任务被抽象出来，他们就可以交给并发编程平台去执行，同时在任务抽象还有另一个重要抽象，那就是生命周期，一个任务的开始，结束，返回结果，都是生命周期中重要的阶段。

那么编程平台必须提供有效安全的管理任务生命周期的API。 四、线程模型 线程模型是Java的本质模型，它无所不在，所以Java开发必须搞清楚底层线程调度细节，不搞清楚当然就会有struts1,struts2的原理搞不清楚的基本灾难（比如在struts2的action中塞入状态，把struts2的action配成单例）。

用线程来抽象并发编程，是比较低级别的抽象，所以难度就大一些，难度级别会根据我们的任务特点有以下几个类别 （1）任务非常独立，不共享，这是最理想的情况，编程压力为0。 (2)共享数据，压力开始增大，必须引入锁，Volatile变量，问题有活跃度和性能危险。

（3）状态依赖，压力再度增大，这时候我们基本上都是求助jdk 提供的同步工具。 五、任务执行 任务是一个抽象体，如果被抽象了出来，下一步就是交给编程平台去执行，在Java中，描述任务的一个基本接口是Runnable，可是这个抽象太有限了，它不能返回值和抛受检查异常，所以Jdk5。

0有另外一个高级抽象Callable。 任务的执行在Jdk中也是一个底级别的Thread，线程有好处，但是大量线程就有大大的坏处，所以如果任务量很多我们并不能就创建大量的线程去服务这些任务，那么Jdk5。

0在任务执行上做了抽象，将任务和任务执行隔离在接口背后，这样我们就可以引入比如线程池的技术来优化执行，优化线程的创建。 任务是有生命周期的，所以Jdk5。

0提供了Future这个对象来描述对象的生命周期，通过这个future可以取到任务的结果甚至取消任务。 六、锁 当然任务之间共享了数据，那么要保证数据的安全，必须提供一个锁机制来协调状态，锁让数据访问原子，但是引入了串行化，降低了并发度，锁是降低程序伸缩性的原罪，锁是引入上下文切换的主要原罪，锁是引入死锁，活锁，优先级倒置的绝对原罪，但是又不能没有锁，在Java中，锁是一个对象，锁提供原子和内存可见性，Volatile变量提供内存可见性不提供原子，原子变量提供可见性和原子，通过原子变量可以构建无锁算法和无锁数据结构，但是这需要高高手才可以办到。

5.Java高并发入门要怎么学习

1、如果不使用框架，纯原生Java编写，是需要了解Java并发编程的，主要就是学习Doug Lea开发的那个java.util.concurrent包下面的API;2、如果使用框架，那么我的理解，在代码层面确实不会需要太多的去关注并发问题，反而是由于高并发会给系统造成很大压力，要在缓存、数据库操作上要多加考虑。

3、但是即使是使用框架，在工作中还是会用到多线程，就拿常见的CRUD接口来说，比如一个非常耗时的save接口，有多耗时呢？我们假设整个save执行完要10分钟，所以，在save的时候，就需要采用异步的方式，也就是单独用一个线程去save，然后直接给前端返回200。

6.Java如何进行并发多连接socket编程呢

Java多个客户端同时连接服务端，在现实生活中用得比较多。

同时执行多项任务，第一想到的当然是多线程了。下面用多线程来实现并发多连接。

import java。。

*; import java。io。

*; public class ThreadServer extends Thread { private Socket client; public ThreadServer(Socket c) { this。 client=c; } public void run() { try { BufferedReader in=new BufferedReader(new InputStreamReader(client。

getInputStream())); PrintWriter out=new PrintWriter(client。 getOutputStream()); Mutil User but can't parallel while (true) { String str=in。

readLine(); System。out。

println(str); out。 println("has receive。

"); out。

flush(); if (str。equals("end")) break; } client。

close(); } catch (IOException ex) { } finally { } } public static void main(String[] args)throws IOException { ServerSocket server=new ServerSocket(8000); while (true) { transfer location change Single User or Multi User ThreadServer mu=new ThreadServer(server。 accept()); mu。

start(); } } }J。

7.如何掌握java多线程,高并发,大数据方面的技能

线程：同一类线程共享代码和数据空间，每个线程有独立的运行栈和程序计数器（PC），线程切换开销小。

（线程是cpu调度的最小单位）线程和进程一样分为五个阶段：创建、就绪、运行、阻塞、终止。多进程是指操作系统能同时运行多个任务（程序）。

多线程是指在同一程序中有多个顺序流在执行。在java中要想实现多线程，有两种手段，一种是继续Thread类，另外一种是实现Runable接口.（其实准确来讲，应该有三种，还有一种是实现Callable接口，并与Future、线程池结合使用。

8.java工程师需要掌握哪些知识

1.Core Java，就是Java基础、JDK的类库，很多童鞋都会说，JDK我懂，但是懂还不足够，知其然还要知其所以然，JDK的源代码写的非常好，要经常查看，对使用频繁的类，比如String， *** 类（List,Map,Set）等数据结构要知道它们的实现，不同的 *** 类有什么区别，然后才能知道在一个具体的场合下使用哪个 *** 类更适合、更高效，这些内容直接看源代码就OK了2.多线程并发编程，现在并发几乎是写服务端程序必须的技术，那对Java中的多线程就要有足够的熟悉，包括对象锁机制、synchronized关键字，concurrent包都要非常熟悉，这部分推荐你看看《Java并发编程实践》这本书，讲解的很详细3.I/O,Socket编程，首先要熟悉Java中Socket编程，以及I/O包，再深入下去就是Java NIO，再深入下去是操作系统底层的Socket实现，了解Windows和Linux中是怎么实现socket的4.JVM的一些知识，不需要熟悉，但是需要了解，这是Java的本质，可以说是Java的母体， 了解之后眼界会更宽阔，比如Java内存模型（会对理解Java锁、多线程有帮助）、字节码、JVM的模型、各种垃圾收集器以及选择、JVM的执行参数（优化JVM）等等，这些知识在《深入Java虚拟机》这本书中都有详尽的解释，或者去oracle网站上查看具体版本的JVM规范.5.一些常用的设计模式，比如单例、模板方法、代理、适配器等等，以及在Core Java和一些Java框架里的具体场景的实现，这个可能需要慢慢积累，先了解有哪些使用场景，见得多了，自己就自然而然会去用。

6.常用数据库（Oracle、MySQL等）、SQL语句以及一般的优化7.JavaWeb开发的框架，比如Spring、iBatis等框架，同样他们的原理才是最重要的，至少要知道他们的大致原理。8.其他一些有名的用的比较多的开源框架和包，ty网络框架，Apache mon的N多包，Google的Guava等等，也可以经常去Github上找一些代码看看。

暂时想到的就这么多吧，1-4条是Java基础，全部的这些知识没有一定的时间积累是很难搞懂的，但是了解了之后会对Java有个彻底的了解，5和6是需要学习的额外技术，7-8是都是基于1-4条的，正所谓万变不离其宗，前4条就是Java的灵魂所在，希望能对你有所帮助9.（补充）学会使用Git。如果你还在用SVN的话，赶紧投入Git的怀抱吧。

9.java 多线程的并发到底是什么意思

一、多线程1、操作系统有两个容易混淆的概念，进程和线程。

进程：一个计算机程序的运行实例，包含了需要执行的指令；有自己的独立地址空间，包含程序内容和数据；不同进程的地址空间是互相隔离的；进程拥有各种资源和状态信息，包括打开的文件、子进程和信号处理。线程：表示程序的执行流程，是CPU调度执行的基本单位；线程有自己的程序计数器、寄存器、堆栈和帧。

同一进程中的线程共用相同的地址空间，同时共享进进程锁拥有的内存和其他资源。2、Java标准库提供了进程和线程相关的API，进程主要包括表示进程的java.lang.Process类和创建进程的java.lang.ProcessBuilder类；表示线程的是java.lang.Thread类，在虚拟机启动之后，通常只有Java类的main方法这个普通线程运行，运行时可以创建和启动新的线程；还有一类守护线程（damon thread），守护线程在后台运行，提供程序运行时所需的服务。

当虚拟机中运行的所有线程都是守护线程时，虚拟机终止运行。3、线程间的可见性：一个线程对进程 *** 享的数据的修改，是否对另一个线程可见可见性问题：a、CPU采用时间片轮转等不同算法来对线程进行调度[java] view plaincopypublic class IdGenerator{ private int value = 0; public int getNext(){ return value++； } } 对于IdGenerator的getNext（)方法，在多线程下不能保证返回值是不重复的：各个线程之间相互竞争CPU时间来获取运行机会，CPU切换可能发生在执行间隙。

以上代码getNext（)的指令序列：CPU切换可能发生在7条指令之间，多个getNext的指令交织在一起。

并发算法之并行排序

大部分排序算法都是串行执行的，当排序元素很多时，使用并行排序算法可以有效利用CPU，提高运算效率，但将串行算法改成并行算法将会极大的增加原有算法的复杂度。

1、分离数据相关性：奇偶交换排序

冒泡排序：如果数据较小，会逐步被交换到前面，对于大的数字会下沉，交换到数组的尾部。

在每次迭代交换过程中，由于每次交换的两个元素存在数据冲突，对于每个元素，它既可能与前面的元素交换，也可能与后面的元素交换，因此很难直接改成并行算法。如果能够解开这种数据的相关性，就可以更容易的使用并行算法，奇偶交换排序就是基于这种思想的。

对于奇偶交换排序，它将排序过程分成两个阶段，奇交换和偶交换。奇交换总是比较奇数索引及其相邻的后续元素，而偶交换总是比较偶数索引及其相邻的后续元素。并且奇交换和偶交换会成对出现，这样才能保证比较和交换涉及到数组中的每一个元素。在每个阶段内，所有的比较和交换是没有数据相关性的，每次比较和交换都可以独立执行。

flag用来记录当前迭代释放发生了数据交换，start用来表示奇交换或偶交换。初始start=0，表示进行偶交换，每次迭代结束切换start状态。如果上次比较交换发生了数据交换，或当前正在进行的是奇交换，循环不会停止，直到不再发生交换，并且当前进行的是偶交换为止。

2、改进的插入排序：希尔排序

插入排序思想：一个未排序的数组可以分为两部分，前半部分是已排序的，后半部分是未排序的，在进行排序时，只需在未排序的部分中选择一个元素，将其插入到前面有序的数组中即可。最终未排序的部分越来越少，直至为0排序完成。

插入排序很难并行化，因为上一次的数据插入依赖于上一次得到的有序序列，多个步骤之间无法并行。

希尔排序将整个数组根据间隔h分割为若干个子数组，子数组相互穿插在一起，每次排序时分别对每一个子数组进行排序。每次排序时总是交换间隔为h的两个元素。在每组排序完成后，可以递减h的值，进行下轮排序，直到h=1，此时等价于一次插入排序。

希尔排序优点：即使一个较小的元素在数组末尾，由于每次元素移动都以间隔h进行，数组末尾的元素可以在很少的交换次数下，被置换到最接近元素最终位置的地方。

改造成并行希尔排序：

--参考文献《实战Java高并发程序设计》

java基础 insert方法问题？

20大进阶架构专题每日送达

1.直接插入排序

经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。

将第一个数和第二个数排序，然后构成一个有序序列

将第三个数插入进去，构成一个新的有序序列。

对第四个数、第五个数……直到最后一个数，重复第二步。

如何写成代码：

首先设定插入次数，即循环次数，for(int i=1;i

设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。

从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。

将当前数放置到空着的位置，即j+1。

代码实现如下：

public void insertSort(int[] a){

int length=a.length;//数组长度，将这个提取出来是为了提高速度。

int insertNum;//要插入的数

for(int i=1;i//插入的次数

insertNum=a[i];//要插入的数

int j=i-1;//已经排序好的序列元素个数

while(j=0a[j]insertNum){//序列从后到前循环，将大于insertNum的数向后移动一格

a[j+1]=a[j];//元素移动一格

j--;

}

a[j+1]=insertNum;//将需要插入的数放在要插入的位置。

}

}

2.希尔排序

对于直接插入排序问题，数据量巨大时。

将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。

再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。

重复第二步，直到k=1执行简单插入排序。

如何写成代码：

首先确定分的组数。

然后对组中元素进行插入排序。

然后将length/2，重复1,2步，直到length=0为止。

代码实现如下：

public void sheelSort(int[] a){

int d = a.length;

while (d!=0) {

d=d/2;

for (int x = 0; x d; x++) {//分的组数

for (int i = x + d; i a.length; i += d) {//组中的元素，从第二个数开始

int j = i - d;//j为有序序列最后一位的位数

int temp = a[i];//要插入的元素

for (; j = 0 temp a[j]; j -= d) {//从后往前遍历。

a[j + d] = a[j];//向后移动d位

}

a[j + d] = temp;

}

}

}

}

3.简单选择排序

常用于取序列中最大最小的几个数时。

(如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。)

遍历整个序列，将最小的数放在最前面。

遍历剩下的序列，将最小的数放在最前面。

重复第二步，直到只剩下一个数。

如何写成代码：

首先确定循环次数，并且记住当前数字和当前位置。

将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。

比对完成后，将最小的值与第一个数的值交换。

重复2、3步。

代码实现如下：

public void selectSort(int[] a) {

int length = a.length;

for (int i = 0; i length; i++) {//循环次数

int key = a[i];

int position=i;

for (int j = i + 1; j length; j++) {//选出最小的值和位置

if (a[j] key) {

key = a[j];

position = j;

}

}

a[position]=a[i];//交换位置

a[i]=key;

}

}

4.堆排序

对简单选择排序的优化。

将序列构建成大顶堆。

将根节点与最后一个节点交换，然后断开最后一个节点。

重复第一、二步，直到所有节点断开。

代码实现如下：

public void heapSort(int[] a){

System.out.println("开始排序");

int arrayLength=a.length;

//循环建堆

for(int i=0;i-1;i++){

//建堆

buildMaxHeap(a,arrayLength-1-i);

//交换堆顶和最后一个元素

swap(a,0,arrayLength-1-i);

System.out.println(Arrays.toString(a));

}

}

private void swap(int[] data, int i, int j) {

// TODO Auto-generated method stub

int tmp=data[i];

data[i]=data[j];

data[j]=tmp;

}

//对data数组从0到lastIndex建大顶堆

private void buildMaxHeap(int[] data, int lastIndex) {

// TODO Auto-generated method stub

//从lastIndex处节点（最后一个节点）的父节点开始

for(int i=(lastIndex-1)/2;i=0;i--){

//k保存正在判断的节点

int k=i;

//如果当前k节点的子节点存在

while(k*2+1=lastIndex){

//k节点的左子节点的索引

int biggerIndex=2*k+1;

//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在

if(biggerIndex //若果右子节点的值较大

if(data[biggerIndex]1]){

//biggerIndex总是记录较大子节点的索引

biggerIndex++;

}

}

//如果k节点的值小于其较大的子节点的值

if(data[k] //交换他们

swap(data,k,biggerIndex);

//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值

k=biggerIndex;

}else{

break;

}

}

}

}

5.冒泡排序

一般不用。

将序列中所有元素两两比较，将最大的放在最后面。

将剩余序列中所有元素两两比较，将最大的放在最后面。

重复第二步，直到只剩下一个数。

如何写成代码：

设置循环次数。

设置开始比较的位数，和结束的位数。

两两比较，将最小的放到前面去。

重复2、3步，直到循环次数完毕。

代码实现如下：

public void bubbleSort(int[] a){

int length=a.length;

int temp;

for(int i=0;i for(int j=0;j-1;j++){

if(a[j]a[j+1]){

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

}

6.快速排序

要求时间最快时。

选择第一个数为p，小于p的数放在左边，大于p的数放在右边。

递归的将p左边和右边的数都按照第一步进行，直到不能递归。

代码实现如下：

public static void quickSort(int[] numbers, int start, int end) {

if (start end) {

int base = numbers; // 选定的基准值（第一个数值作为基准值）

int temp; // 记录临时中间值

int i = start, j = end;

do {

while ((numbers[i] base) (i end))

i++;

while ((numbers[j] base) (j start))

j--;

if (i = j) {

temp = numbers[i];

numbers[i] = numbers[j];

numbers[j] = temp;

i++;

j--;

}

} while (i = j);

if (start j)

quickSort(numbers, start, j);

if (end i)

quickSort(numbers, i, end);

}

}

7.归并排序

速度仅次于快排，内存少的时候使用，可以进行并行计算的时候使用。

选择相邻两个数组成一个有序序列。

选择相邻的两个有序序列组成一个有序序列。

重复第二步，直到全部组成一个有序序列。

代码实现如下：

public static void mergeSort(int[] numbers, int left, int right) {

int t = 1;// 每组元素个数

int size = right - left + 1;

while (t size) {

int s = t;// 本次循环每组元素个数

t = 2 * s;

int i = left;

while (i + (t - 1) size) {

merge(numbers, i, i + (s - 1), i + (t - 1));

i += t;

}

if (i + (s - 1) right)

merge(numbers, i, i + (s - 1), right);

}

}

private static void merge(int[] data, int p, int q, int r) {

int[] B = new int[data.length];

int s = p;

int t = q + 1;

int k = p;

while (s = q t = r) {

if (data[s] = data[t]) {

B[k] = data[s];

s++;

} else {

B[k] = data[t];

t++;

}

k++;

}

if (s == q + 1)

B[k++] = data[t++];

else

B[k++] = data[s++];

for (int i = p; i = r; i++)

data[i] = B[i];

}

8.基数排序

用于大量数，很长的数进行排序时。

将所有的数的个位数取出，按照个位数进行排序，构成一个序列。

将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。

代码实现如下：

public void sort(int[] array) {

//首先确定排序的趟数;

int max = array[0];

for (int i = 1; i array.length; i++) {

if (array[i] max) {

max = array[i];

}

}

int time = 0;

//判断位数;

while (max 0) {

max /= 10;

time++;

}

//建立10个队列;

List queue = new ArrayList ();

for ( int i = 0; i 10; i++) {

ArrayList queue1 = new ArrayList ();

queue.add(queue1);

}

//进行time次分配和收集;

for ( int i = 0; i time; i++) {

//分配数组元素;

for ( int j = 0; j array.length; j++) {

//得到数字的第time+1位数;

int x = array[j] % ( int) Math. pow( 10, i + 1) / ( int) Math. pow( 10, i);

ArrayList queue2 = queue.get(x);

queue2.add( array[j]);

queue. set(x, queue2);

}

int count = 0; //元素计数器;

//收集队列元素;

for ( int k = 0; k 10; k++) {

while ( queue.get(k).size() 0) {

ArrayList queue3 = queue.get(k);

array[count] = queue3.get( 0);

queue3.remove( 0);

count++;

}

}

}

}

来源：KaelQ

地址：

获取方式：点“在看”，V信关注师长的小号：编程最前线并回复面试领取，更多精彩陆续奉上。