分类： Android技术

Android面试题线程篇，由本人整理汇总，后续将推出系列篇，如果喜欢请持续关注和推荐。

开启线程的三种方式？

java有三种创建线程的方式，分别是继承Thread类、实现Runable接口和使用线程池

线程池：

Android中常见的线程池有四种，FixedThreadPool、CachedThreadPool、ScheduledThreadPool、SingleThreadExecutor。

FixedThreadPool线程池是通过Executors的new FixedThreadPool方法来创建。它的特点是该线程池中的线程数量是固定的。即使线程处于闲置的状态，它们也不会被回收，除非线程池被关闭。当所有的线程都处于活跃状态的时候，新任务就处于队列中等待线程来处理。注意，FixedThreadPool只有核心线程，没有非核心线程。
CachedThreadPool线程池是通过Executors的newCachedThreadPool进行创建的。它是一种线程数目不固定的线程池，它没有核心线程，只有非核心线程，当线程池中的线程都处于活跃状态，就会创建新的线程来处理新的任务。否则就会利用闲置的线程来处理新的任务。线程池中的线程都有超时机制，这个超时机制时长是60s，超过这个时间，闲置的线程就会被回收。这种线程池适合处理大量并且耗时较少的任务。这里得说一下，CachedThreadPool的任务队列，基本都是空的。
ScheduledThreadPool线程池是通过Executors的newScheduledThreadPool进行创建的，它的核心线程是固定的，但是非核心线程数是不固定的，并且当非核心线程一处于空闲状态，就立即被回收。这种线程适合执行定时任务和具有固定周期的重复任务。
SingleThreadExecutor线程池是通过Executors的newSingleThreadExecutor方法来创建的，这类线程池中只有一个核心线程，也没有非核心线程，这就确保了所有任务能够在同一个线程并且按照顺序来执行，这样就不需要考虑线程同步的问题。
sleep(), wait()的区别

sleep不释放同步锁，自动唤醒，需要try catch, wait释放同步锁，需要notify来唤醒
sleep是线程的方法 wait是Object的方法
谈谈wait/notify关键字的理解

等待对象的同步锁,需要获得该对象的同步锁才可以调用这个方法,否则编译可以通过，但运行时会收到一个异常：IllegalMonitorStateException。

调用任意对象的 wait() 方法导致该线程阻塞，该线程不可继续执行，并且该对象上的锁被释放。

唤醒在等待该对象同步锁的线程(只唤醒一个,如果有多个在等待),注意的是在调用此方法的时候，并不能确切的唤醒某一个等待状态的线程，而是由JVM确定唤醒哪个线程，而且不是按优先级。

调用任意对象的notify()方法则导致因调用该对象的 wait()方法而阻塞的线程中随机选择的一个解除阻塞（但要等到获得锁后才真正可执行）。

Thread中的start()和run()方法有什么区别

start()方法是用来启动新创建的线程，而start()内部调用了run()方法，这和直接调用run()方法是不一样的，如果直接调用run()方法，

如何控制某个方法允许并发访问线程的个数？

semaphore.acquire() 请求一个信号量，这时候的信号量个数-1（一旦没有可使用的信号量，也即信号量个数变为负数时，再次请求的时候就会阻塞，直到其他线程释放了信号量）
semaphore.release() 释放一个信号量，此时信号量个数+1
什么导致线程阻塞？线程如何关闭？

阻塞式方法是指程序会一直等待该方法完成期间不做其他事情，ServerSocket的accept()方法就是一直等待客户端连接。这里的阻塞是指调用结果返回之前，当前线程会被挂起，直到得到结果之后才会返回。此外，还有异步和非阻塞式方法在任务完成前就返回。

一种是调用它里面的stop()方法

另一种就是你自己设置一个停止线程的标记 （推荐这种）

如何保证线程安全？

1.synchronized；
2.Object方法中的wait,notify；
3.ThreadLocal机制 来实现的。
如何实现线程同步？

1、synchronized关键字修改的方法。
2、synchronized关键字修饰的语句块
3、使用特殊域变量（volatile）实现线程同步
线程间操作List

List list = Collections.synchronizedList(new ArrayList());

谈谈对Synchronized关键字，类锁，方法锁，重入锁的理解

java的对象锁和类锁：java的对象锁和类锁在锁的概念上基本上和内置锁是一致的，但是，两个锁实际是有很大的区别的，对象锁是用于对象实例方法，或者一个对象实例上的，类锁是用于类的静态方法或者一个类的class对象上的。我们知道，类的对象实例可以有很多个，但是每个类只有一个class对象，所以不同对象实例的对象锁是互不干扰的，但是每个类只有一个类锁。但是有一点必须注意的是，其实类锁只是一个概念上的东西，并不是真实存在的，它只是用来帮助我们理解锁定实例方法和静态方法的区别的

synchronized 和volatile 关键字的区别

1.volatile本质是在告诉jvm当前变量在寄存器（工作内存）中的值是不确定的，需要从主存中读取；synchronized则是锁定当前变量，只有当前线程可以访问该变量，其他线程被阻塞住。
2.volatile仅能使用在变量级别；synchronized则可以使用在变量、方法、和类级别的
3.volatile仅能实现变量的修改可见性，不能保证原子性；而synchronized则可以保证变量的修改可见性和原子性
4.volatile不会造成线程的阻塞；synchronized可能会造成线程的阻塞。
5.volatile标记的变量不会被编译器优化；synchronized标记的变量可以被编译器优化
ReentrantLock 、synchronized和volatile比较

java在过去很长一段时间只能通过synchronized关键字来实现互斥，它有一些缺点。比如你不能扩展锁之外的方法或者块边界，尝试获取锁时不能中途取消等。Java 5 通过Lock接口提供了更复杂的控制来解决这些问题。 ReentrantLock 类实现了 Lock，它拥有与 synchronized 相同的并发性和内存语义且它还具有可扩展性。

线程同步的问题，常用的线程同步

1.sycn：保证了原子性、可见性、有序性
2.锁：保证了原子性、可见性、有序性
1.自旋锁:可以使线程在没有取得锁的时候，不被挂起，而转去执行一个空循环。
1.优点:线程被挂起的几率减少，线程执行的连贯性加强。用于对于锁竞争不是很激烈，锁占用时间很短的并发线程。
2.缺点:过多浪费CPU时间，有一个线程连续两次试图获得自旋锁引起死锁
2.阻塞锁:没得到锁的线程等待或者挂起，Sycn、Lock
3.可重入锁:一个线程可多次获取该锁，Sycn、Lock
4.悲观锁:每次去拿数据的时候都认为别人会修改，所以会阻塞全部其他线程 Sycn、Lock
5.乐观锁:每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号等机制。cas
6.显示锁和内置锁:显示锁用Lock来定义、内置锁用synchronized。
7.读-写锁:为了提高性能，Java提供了读
3.volatile
1.只能保证可见性，不能保证原子性
2.自增操作有三步，此时多线程写会出现问题
4.cas
1.操作:内存值V、旧的预期值A、要修改的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做并返回false。
2.解释:本地副本为A，共享内存为V，线程A要把V修改成B。某个时刻线程A要把V修改成B，如果A和V不同那么就表示有其他线程在修改V，此时就表示修改失败，否则表示没有其他线程修改，那么把V改成B。
3.局限:如果V被修改成V1然后又被改成V，此时cas识别不出变化，还是认为没有其他线程在修改V，此时就会有问题
4.局限解决:将V带上版本。
5.线程不安全到底是怎么回事：
1.一个线程写，多个线程读的时候，会造成写了一半就去读
2.多线程写，会造成脏数据
有三个线程T1，T2，T3，怎么确保它们按顺序执行？

在多线程中有多种方法让线程按特定顺序执行，你可以用线程类的join()方法在一个线程中启动另一个线程，另外一个线程完成该线程继续执行。为了确保三个线程的顺序你应该先启动*后一个(T3调用T2，T2调用T1)，这样T1就会先完成而T3*后完成。

Android的多线程模型有哪几种？

Android提供了四种常用的操作多线程的方式，分别是：

Handler+Thread
AsyncTask
ThreadPoolExecutor
IntentService
Android多线程的实现方式有哪些?

Thread & AsyncTask
Thread 可以与Loop 和 Handler 共用建立消息处理队列
AsyncTask 可以作为线程池并行处理多任务
多线程的优劣

使用多进程显而易见的好处就是分担主进程的内存压力。我们的应用越做越大，内存越来越多，将一些独立的组件放到不同的进程，它就不占用主进程的内存空间了。当然还有其他好处，有心人会发现Android后台进程里有很多应用是多个进程的，因为它们要常驻后台，特别是即时通讯或者社交应用，不过现在多进程已经被用烂了。典型用法是在启动一个不可见的轻量级私有进程，在后台收发消息，或者做一些耗时的事情，或者开机启动这个进程，然后做监听等。还有就是防止主进程被杀守护进程，守护进程和主进程之间相互监视，有一方被杀就重新启动它。 坏处的话，多占用了系统的空间，大家都这么用的话系统内存很容易占满而导致卡顿。消耗用户的电量。应用程序架构会变复杂，应为要处理多进程之间的通信。这里又是另外一个问题了。

AsyncTask的工作原理

AsyncTask是Android本身提供的一种轻量级的异步任务类。它可以在线程池中执行后台任务，然后把执行的进度和*终的结果传递给主线程更新UI。实际上，AsyncTask内部是封装了Thread和Handler。虽然AsyncTask很方便的执行后台任务，以及在主线程上更新UI，但是，AsyncTask并不合适进行特别耗时的后台操作，对于特别耗时的任务，个人还是建议使用线程池。

HandlerThread是什么

MessageQueue + Looper + Handler

IntentService是什么

含有HandlerThread的Service，可以多次startService()来多次在子线程中进行 onHandlerIntent()的调用。

线程间如何通信

我们知道线程是CPU调度的*小单位。在Android中主线程是不能够做耗时操作的，子线程是不能够更新UI的。而线程间通信的方式有很多，比如广播，Eventbus，接口回掉，在Android中主要是使用handler。handler通过调用sendmessage方法，将保存消息的Message发送到Messagequeue中，而looper对象不断的调用loop方法，从messageueue中取出message，交给handler处理，从而完成线程间通信。

Android面试题算法篇，由本人整理汇总，后续将继续推出系列篇，如果喜欢请持续关注和推荐，更多精彩内容

红黑树特点

1.root节点和叶子节点是黑色
2.红色节点后必须为黑色节点
3.从root到叶子每条路径的黑节点数量相同
实现阶乘

//采用递归法
public static long factorial(long number) {
if (number <= 1)
return 1;
else
return number * factorial(number – 1);
}
//采用循环连乘法
public static int fact(int num){
int temp=1;
int factorial=1;
while(num>=temp){
factorial=factorial*temp;
temp++;
}
return factorial;
}
二分查找

//递归法
int binarySearch(int array[], int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high – low) / 2;
if (array[mid] > target)
return binarysearch(array, low, mid – 1, target);
if (array[mid] < target)
return binarysearch(array, mid + 1, high, target);
return mid;
}
//循环法
int binarySearch2(int a[], int key) {
int low = 0;
int high = a.length – 1;
while (low <= high) {
int mid = low + (high – low) / 2;
if (a[mid] > key)
high = mid – 1;
else if (a[mid] < key)
low = mid + 1;
else
return mid;
}
return -1;
}
二分查找中值的计算
这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：
算法一： mid = (low + high) / 2
算法二： mid = low + (high – low)/2
乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。但是实际上，区别是存在的。算法一的做法，在*端情况下，(low+high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。

二分查找法的缺陷
二分查找法的O(logn)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。
数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。
解决这些缺陷问题更好的方法应该是使用二叉查找树了，*好自然是自平衡二叉查找树了，既能高效的（O(n log n)）构建有序元素集合，又能如同二分查找法一样快速（O(log n)）的搜寻目标数。

用两个栈实现队列

题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：
压入元素直接压入stack1 删除元素先查看stack2是否为空，非空则弹出；空则将stack1中元素取出，置于stack2中

代码：

public class StackQueue {

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node){
stack1.push(node);
}

public int pop(){
if(stack2.empty()){
while(!stack1.empty())
stack2.push(stack1.pop());
}
return stack2.pop();
}
递归和迭代的区别是什么，各有什么优缺点？

程序调用自身称为递归，利用变量的原值推出新值称为迭代。
递归的优点大问题转化为小问题，可以减少代码量，同时代码精简，可读性好；
缺点就是递归调用浪费了空间，而且递归太深容易造成堆栈的溢出。
迭代的好处就是代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销；
缺点就是代码不如递归简洁
判断101-200之间有多少个素数，并输出所有素数
素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ 间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。例如 16 能被 2、4、8 整除，16=28，2 小于 4，8 大于 4，16=44，4=√16，因此只需判定在 2~4 之间有无因子即可。

public class mainCase{
public static void main(String args[]){
int i=0;
for(i=101;i<=200;i++)
if(math.isPrime(i)==true)
System.out.println(i);
}
}
class math
{
//方法1
public static boolean isPrime(int x)
{
for (int i=2;i<=x/2;i++)
if (x%2==0)
return false;
return true;
}

//方法2
public static boolean isPrime2(int m)
{
int k=(int)sqrt((double)m);
for (int i=2;i<=k;i++)
if (m%i==0)
return false;
return true;
}
}
字符串小写字母转换成大写字母

public String toUpperCase(String str)
{
if (str != null && str.length() > 0) {
for (int i=0; i<str.length(); i++) {
char c = str.charAt(i);
c += 32;
}
}
return str;
}
进制转换：给定一个十进制数 n 和 一个整数 k, 将 十进制数 n 转换成 k进制数

public String hexConversion(int n, int k) {
StringBuffer resultNumber = new StringBuffer();
tenToK(resultNumber, n, k);
System.out.println(“n:k:result: ” + n +” “+ k + ” ” + resultNumber.toString());

return resultNumber.toString();
}

private void tenToK(StringBuffer stringBuffer, int n, int k) {
int integral = n/k;
int mode = n % k;
stringBuffer.insert(0, mode);
if (integral >= k) {
tenToK(stringBuffer, integral, k);
} else if (integral > 0) {
stringBuffer.insert(0, integral);
}
}
位运算实现加法

public int aplusb(int a, int b) {
int sum_without_carry, carry;

sum_without_carry = a^b; //没有进位的和
carry = (a&b)<<1; //进位
if(carry==0) {
return sum_without_carry;
} else {
return aplusb(sum_without_carry, carry);
}
}
二叉树排序树

首先定义节点类

public class TreeNode {
Object obj;
TreeNode parent;
TreeNode lchild;
TreeNode rchild;

public TreeNode(int obj) {
this.obj = obj;
}
}
然后创建一个树类

public class Tree {

/**
* 先序遍历二叉树
* @param root
*/
public void Fprint(TreeNode root){
if(root!=null){
System.out.println(root.obj);
Fprint(root.lchild);
Fprint(root.rchild);
}
}

/**
* 中序遍历二叉树
* @param root
*/
public void Mprint(TreeNode root){
if(root!=null){
Mprint(root.lchild);
System.out.println(root.obj);

Mprint(root.rchild);
}
}

/**
* 根据一个int数组建立二叉排序树
* @param a 数组
* @return
*/
public TreeNode Build(int[] a){
if(a.length==0){
return null;
}
TreeNode root = new TreeNode(a[0]);
for(int i=1;i<a.length;i++){
TreeNode newnode = new TreeNode(a[i]);
sort(root,newnode);
}
return root;
}
/**
* 在二叉排序树中添加一个节点
* @param root 二叉树的根节点
* @param newnode 新加入的加点
* @return
*/
public void sort(TreeNode root,TreeNode newnode){
TreeNode node = root;
if((Integer)newnode.obj<=(Integer)node.obj){
if(node.lchild==null){
newnode.parent = node;
node.lchild = newnode;
}else{
sort(node.lchild,newnode);
}
}else{
if(node.rchild==null){
newnode.parent = node;
node.rchild = newnode;
}else{
sort(node.rchild,newnode);
}
}
}
}
创建二叉排序树的时候随便传入一个int型数组a[]
然后通过自顶向下的方式一个一个的将a[0]—a[n]个元素创建的节点类一个一个的拼接到树上
此后只需要再创建一个主函数类来调用便行了

public class Test {

public static void main(String[] args) {
int a[] = {100,35,3,44,212,453};
Tree t = new Tree();
TreeNode root = t.Build(a);
t.Mprint(root);
}

}
这样便可通过创建二叉排序树并且中序遍历该二叉树的方式，来将一组混乱的数据整理成一组从小到大的数据了。

冒泡排序

算法描述：对于给定的n个记录，从*个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和交换后，n个记录中的*大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。

package sorting;

/**
* 冒泡排序
* 平均O(n^2),*好O(n),*坏O(n^2);空间复杂度O(1);稳定;简单
* @author zeng
*
*/
public class BubbleSort {

public static void bubbleSort(int[] a){

int n = a.length;
int temp = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]<a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}

public static void main(String[] args){
int[] a ={49,38,65,97,76,13,27,50};
bubbleSort(a);
for(int j:a)
System.out.print(j+” “);
}
}
插入排序

算法描述：对于给定的一个数组，初始时假设*个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至*后一个记录插入到有序序列中为止。

package sorting;

/**
* 插入排序
* 平均O(n^2),*好O(n),*坏O(n^2);空间复杂度O(1);稳定;简单
* @author zeng
*
*/
public class InsertionSort {

public static void insertionSort(int[] a) {
int tmp;
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j–) {
if (a[j] < a[j – 1]) {
tmp = a[j – 1];
a[j – 1] = a[j];
a[j] = tmp;
}
}
}
}

public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
insertionSort(a);
for (int i : a)
System.out.print(i + ” “);
}
}
选择排序

算法描述：对于给定的一组记录，经过*轮比较后得到*小的记录，然后将该记录与*个记录的位置进行交换；接着对不包括*个记录以外的其他记录进行第二轮比较，得到*小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。

package sorting;

/**
* 选择排序
* 平均O(n^2),*好O(n^2),*坏O(n^2);空间复杂度O(1);不稳定;简单
* @author zeng
*
*/
public class SelectionSort {

public static void selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int k = i;
// 找出*小值的小标
for (int j = i + 1; j < n; j++) {
if (a[j] < a[k]) {
k = j;
}
}
// 将*小值放到排序序列末尾
if (k > i) {
int tmp = a[i];
a[i] = a[k];
a[k] = tmp;
}
}
}

public static void main(String[] args) {
int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
selectionSort(b);
for (int i : b)
System.out.print(i + ” “);
}
}
快速排序

算法描述：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

package sorting;

/**
* 快速排序
* 平均O(nlogn),*好O(nlogn),*坏O(n^2);空间复杂度O(nlogn);不稳定;较复杂
* @author zeng
*
*/
public class QuickSort {

public static void sort(int[] a, int low, int high) {
if(low>=high)
return;
int i = low;
int j = high;
int key = a[i];
while (i < j) {
while (i < j && a[j] >= key)
j–;
a[i++] = a[j];
while (i < j && a[i] <= key)
i++;
a[j–] = a[i];
}
a[i] = key;
sort(a,low,i-1);
sort(a,i+1,high);
}

public static void quickSort(int[] a) {
sort(a, 0, a.length-1);
for(int i:a)
System.out.print(i+” “);
}

public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
quickSort(a);
}
}
归并排序

算法描述：对于给定的一组记录，首先将每两个相邻的长度为1的子序列进行归并，得到 n/2（向上取整）个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。

package sorting;

/**
* 归并排序
* 平均O(nlogn),*好O(nlogn),*坏O(nlogn);空间复杂度O(n);稳定;较复杂
* @author zeng
*
*/
public class MergeSort {

public static void merge(int[] a, int start, int mid,
int end) {
int[] tmp = new int[a.length];
System.out.println(“merge ” + start + “~” + end);
int i = start, j = mid + 1, k = start;
while (i != mid + 1 && j != end + 1) {
if (a[i] < a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while (i != mid + 1)
tmp[k++] = a[i++];
while (j != end + 1)
tmp[k++] = a[j++];
for (i = start; i <= end; i++)
a[i] = tmp[i];
for (int p : a)
System.out.print(p + ” “);
System.out.println();
}

static void mergeSort(int[] a, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(a, start, mid);// 左边有序
mergeSort(a, mid + 1, end);// 右边有序
merge(a, start, mid, end);
}
}

public static void main(String[] args) {
int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
mergeSort(b, 0, b.length – 1);
}
}
希尔排序

算法描述：先将待排序序列的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序”后，再对所有元素进行一次直接插入排序。

package sorting;

/**
* 希尔排序
* 平均O(nlogn),*坏O(nlogn);空间复杂度O(1);不稳定;较复杂
* @author zeng
*
*/
public class ShellSort {

public static void shellSort(int[] a) {
int n = a.length;
int d = n / 2;
while (d > 0) {
for (int i = d; i < n; i++) {
int j = i – d;
while (j >= 0 && a[j] > a[j + d]) {
int tmp = a[j];
a[j] = a[j + d];
a[j + d] = tmp;
j = j – d;
}
}
d = d / 2;
}
}

public static void main(String[] args) {
int[] b = { 49, 38, 65, 97, 76, 13, 27, 50 };
shellSort(b);
for (int i : b)
System.out.print(i + ” “);
}
}
基数排序

算法思想：依次按个位、十位…来排序，每一个pos都有分配过程和收集过程，array[i][0]记录第i行数据的个数。

package sorting;

/**
* 基数排序
* 平均O(d(n+r)),*好O(d(n+r)),*坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
* d为位数,r为分配后链表的个数
* @author zeng
*
*/
public class RadixSort {

//pos=1表示个位，pos=2表示十位
public static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos – 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}

//求得*大位数d
public static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else
break;
}
return d;
}

public static void radixSort(int[] a, int d) {

int[][] array = new int[10][a.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;// array[i][0]记录第i行数据的个数
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) {// 分配过程
int row = getNumInPos(a[i], pos);
int col = ++array[row][0];
array[row][col] = a[i];
}
for (int row = 0, i = 0; row < 10; row++) {// 收集过程
for (int col = 1; col <= array[row][0]; col++) {
a[i++] = array[row][col];
}
array[row][0] = 0;// 复位，下一个pos时还需使用
}
}
}

public static void main(String[] args) {
int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };
radixSort(a, getMaxWeishu(a));
for (int i : a)
System.out.print(i + ” “);
}
}

堆排序

算法描述：对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的*后一个元素与堆顶元素进行交换后，堆的*后一个元素即为*大记录；接着将前（n-1）个元素重新调整为一个大顶堆，再将堆顶元素与当前堆的*后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩下一个元素时为止。

package sorting;

/**
* 堆排序
* 平均O(nlogn),*好O(nlogn),*坏O(nlogn);空间复杂度O(1);不稳定;较复杂
* @author zeng
*
*/
public class HeapSort {

public static void heapSort(int[] a) {
int i;
int len = a.length;
// 构建堆
for (i = len / 2 – 1; i >= 0; i–)
heapAdjust(a, i, len – 1);
//交换堆顶元素与*后一个元素的位置
for (i = len – 1; i > 0; i–) {
int tmp = a[0];
a[0] = a[i];
a[i] = tmp;
heapAdjust(a, 0, i – 1);
}
}

public static void heapAdjust(int[] a, int pos, int len) {
int child = 2 * pos + 1;
int tmp = a[pos];
while (child <= len) {
if (child < len && a[child] < a[child + 1])
child++;
if (a[child] > tmp) {
a[pos] = a[child];
pos = child;
child = 2 * pos + 1;
} else
break;
}
a[pos] = tmp;
}

public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
heapSort(a);
for (int i : a)
System.out.print(i + ” “);
}
}

本文完~