算法：
选择排序
public void selectSort() {
int main = 0;
long tmp = 0L;
for (int i = 0; i < elems-1; i++) {
if (arr[j] < arr[min]) {
min = j;
}
}
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
插入排序
public void insertSort() {
long select = 0L;
for (int i = 11; i < elems; i++) {
select = arr[i];
int j = 0;
for (j = i; j > 0 && arr[j - 1] >= select; j--) {
arr[j] = arr[j - 1];
}
arr[j] = select;
}
}
冒泡排序
int[] arr = {50,15,56,23,54,84,58,45,21};
for(int i = 0; i < arr.length; i++) {//外层循环控制排序趟数
for(int j = 0; j < arr.length-1-i; j++) {//内层循环控制每一趟排序多少次
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
数组数据结构
数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。
优点：
1.有序
2.连续
3.查询快，根据下标一次计算就可以查到
缺点：
1.插入和删除效率低
2.不利于扩展，数组定义的空间不够时要重新定义数组
3.数组大小固定，不能动弹拓展
链表数据结构
链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了
优点：
1.插入删除速度快
2.内存利用率高，不会浪费内存
3.大小没有固定，拓展很灵活
缺点：
不能随机查找，必须从第一个开始遍历，查找效率低
线性表
1.链式存储
LinkedList
对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
数据元素之间具有一种线性的或“一对一”的逻辑关系。
第一个数据元素没有前驱，这个数据元素被称为开始节点；
最后一个数据元素没有后继，这个数据元素被称为终端节点；
除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
2.顺序存储
ArrayList
所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。
在线性表中逻辑上相邻的数据元素，在物理存储上也是相邻的。
存储密度高，但要预先分配“足够应用”的存储空间，这可能会造成存储空间的浪费。
便于随机存储。
不便于插入和删除操作，这是因为在顺序表上进行的插入和删除操作会引起大量数据元素的移动。
栈和队列
栈：后进先出（LIFO-last in first out）:最后插入的元素最先出来。
队列：先进先出（FIFO-first in first out）:最先插入的元素最先出来。
用数组实现栈
由于数组大小未知，如果每次插入元素都扩展一次数据（每次扩展都意味着构建一个新数组，然后把旧数组复制给新数组），那么性能消耗相当严重。
这里使用贪心算法，数组每次被填满后，加入下一个元素时，把数组拓展成现有数组的两倍大小。
每次移除元素时，检测数组空余空间有多少。当数组里的元素个数只有整个数组大小的四分之一时，数组减半。
为什么不是当数组里的元素个数只有整个数组大小的二分之一时，数组减半？考虑以下情况：数组有4个元素，数组大小为4个元素空间。此时，加一个元素，数组拓展成8个空间；再减一个元素，数组缩小为4个空间；如此循环，性能消耗严重。
用数组实现队列
实现队列与栈类似：
数组每次被填满后，加入下一个元素时，把数组拓展成现有数组的两倍大小。
每次移除元素时，检测数组空余空间有多少。当数组里的元素个数只有整个数组大小的四分之一时，数组减半。
不同之处在于：
由于是先进先出，移除是从队列的最前端开始的。所以当我们移除数个数据后，队列数据是存储在数组的中间部分的。令队列数据的尾端数据ID为Num,首端数据ID为HeadIndex，则Num - HeadIndex为队列数据元素个数。
当队列数据元素个数为整个数组空间的四分之一时，数组减半，且队列数据左移至数组最左端。即Num-=HeadIndex；HeadIndex=0；
HashMap原理
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
HashMap实现了Map接口，Map接口对键值对进行映射。Map中不允许重复的键。
HashSet
HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。
HashMap和HashTable区别
HashMap和Hashtable都实现了Map接口，但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有：线程安全性，同步(synchronization)，以及速度。
HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。
HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
HashMap不能保证随着时间的推移Map中的元素次序是不变的。
线程，进程
1.线程是操作系统能够进行运算调度的最小单位，它被包含在进程之中，是进程中的实际运作单位。程序员可以通过它进行多处理器编程，你可以使用多线程对运算密集型任务提速。
2.一个进程是一个独立(self contained)的运行环境，它可以被看作一个程序或者一个应用。而线程是在进程中执行的一个任务。线程是进程的子集，一个进程可以有很多线程，每条线程并行执行不同的任务。不同的进程使用不同的内存空间，而所有的线程共享一片相同的内存空间
线程间如何通信通信
当线程间是可以共享资源时，线程间通信是协调它们的重要的手段。Object类中wait()\notify()\notifyAll()方法可以用于线程间通信关于资源的锁的状态。点击这里有更多关于线程wait, notify和notifyAll.
方法wait()的作用：使当前执行代码的线程进行等待，wait()方法是Object类的方法，该方法用来将当前线程置入“预执行队列”中，并且在wait()所在的代码行处停止执行，直到接到通知或被中断为止。在调用wait()之前，线程必须获得该对象的对象级别锁，即只能在同步方法或同步块中调用wait()方法。在执行wait()方法后，当前线程释放锁。在从wait()返回前，线程与其他线程竞争重新获得锁。如果调用wait()方法时没有持有适当的锁，则抛出IllegalMonitorStateException异常,它是RuntimeException的一个子类，因此，不需要try-catch语句进行捕捉异常。
方法notify()的作用：也要在同步方法或同步块中调用，即在调用前，线程也必须获得该对象的对象级别锁。如调用notify()时没有持有适当的锁，也会抛出IllegalMonitorStateException。该方法用来通知那些可能等待该对象的对象锁的其他线程，如果有多个线程等待，则由线程规划器随机挑选出其中一个呈wait状态的线程，对其发出通知notify，并使它等待获取该对象的对象锁。需要说明的是，在执行notify()方法后，当前线程不会马上释放该对象锁，呈wait状态的线程也并不能马上获取该对象锁，到等到执行notify()方法的线程将程序执行完，也就是退出synchronized代码块后，当前线程才会释放锁，而呈wait状态所在的线程才可以获取该对象锁。当第一个获得了该对象锁的wait线程运行完毕以后，它会释放掉该对象锁，此时如果该对象没有再次使用notify语句，则即便该对象已经空闲，其他wait状态等待的线程由于没有得到该对象的通知，还会继续阻塞在wait状态，直到这个对象发出一个notify或notifyAll。
volitale和synchronized的区别
1.volitale关键字提供了一个功能，就是被其修饰的变量在被修改后会被强制刷入到主内存中，其他处理器的缓存由于遵守了缓存一致性原则，会把这个变量的值从主内存中加载到自己的缓存中，因此在并发编程中保证了变量的可见性。
2.volitale关键字会禁止指令重排，从而来保证有序性
3.volitale关键字不能保证原子性
1.synchronized可以保证原子性，通过字节码指令monitorenter和monitorexit。
2.synchronized可以保证可见性
3.synchronized关键字保证同一时刻只允许一条线程操作，从而保证了有序性
android中如何处理多线程并发
android中很多操作需要在主线程中执行，比如UI的操作，点击事件等等，但是如果主线程操作太多，占有的执行时间过长就会出现前面我们说的卡顿现象。为了减轻主线程操作过多，避免出现卡顿的现象，我们把一些操作复杂的消耗时间长的任务放到线程池中去执行。
处理多线程并发，android中常见的几种线程类：
1.AsyncTask
为UI线程与工作线程之间进行快速的切换提供一种简单便捷的机制。适用于当下立即需要启动，但是异步执行的生命周期短暂的使用场景。它提供了一种简便的异步处理机制，但是它又同时引入了一些令人厌恶的麻烦。一旦对AsyncTask使用不当，很可能对程序的性能带来负面影响，同时还可能导致内存泄露。
使用AsyncTask需要注意的问题：
a)在AsyncTask中所有的任务都是被线性调度执行的，他们处在同一个任务队列当中，按顺序逐个执行。一旦有任务执行时间过长，队列中其他任务就会阻塞。(阻塞以后我们可以使用AsyncTask.executeOnExecutor()让AsyncTask变成并发调度)
b)AsyncTask对正在执行的任务不具备取消的功能，所以我们要在任务代码中添加取消的逻辑
c)AsyncTask使用不当会导致内存泄漏
2.HandlerThread
为某些回调方法或者等待某些任务的执行设置一个专属的线程，并提供线程任务的调度机制。
HandlerThread中包含了Looper,Handler,MessageQueue
Looper: 能够确保线程持续存活并且可以不断的从任务队列中获取任务并进行执行。
Handler: 能够帮助实现队列任务的管理，不仅仅能够把任务插入到队列的头部，尾部，还可以按照一定的时间延迟来确保任务从队列中能够来得及被取消掉。
MessageQueue: 使用Intent，Message，Runnable作为任务的载体在不同的线程之间进行传递。
把上面三个组件打包到一起进行协作，这就是HandlerThread
3.IntentService
适合于执行由UI触发的后台Service任务，并可以把后台任务执行的情况通过一定的机制反馈给UI。
默认的Service是执行在主线程的，可是通常情况下，这很容易影响到程序的绘制性能(抢占了主线程的资源).
我们可以选择使用IntentService来实现异步操作。IntentService继承自普通Service同时又在内部创建了一个HandlerThread，在onHandlerIntent()的回调里面处理扔到IntentService的任务。所以IntentService就不仅仅具备了异步线程的特性，还同时保留了Service不受主页面生命周期影响的特点。
使用IntentService需要注意的问题：
a)因为IntentService内置的是HandlerThread作为异步线程，所以每一个交给IntentService的任务都将以队列的方式逐个被执行到，一旦队列中有某个任务执行时间过长，那么就会导致后续的任务都会被延迟处理。
b)通常使用到IntentService的时候，我们会结合使用BroadcastReceiver把工作线程的任务执行结果返回给主UI线程。使用广播容易引起性能问题，我们可以使用LocalBroadcastManager来发送只在程序内部传递的广播，从而提升广播的性能。我们也可以使用runOnUiThread()快速回调到主UI线程。
c)包含正在运行的IntentService的程序相比起纯粹的后台程序更不容易被系统杀死，该程序的优先级是介于前台程序与纯后台程序之间的。
4.Loader
对于3.0后ContentProvider中的耗时操作，推荐使用Loader异步加载数据机制。相对其他加载机制。
Loader有那些优点？
a)提供异步加载数据机制
b)对数据源变化进行监听，实时更新数据
c)在Activity配置发生变化（如横竖屏切换）时不用重复加载数据
d)适用于任何Activity和Fragment
使用实例--获取手机中的所有图片
参考代码：
getLoaderManager().initLoader(LOADER_TYPE, null, mLoaderCallback);
LoaderManager.LoaderCallbacks<Cursor> mLoaderCallback = new LoaderManager.LoaderCallbacks<Cursor>() {
private final String[] IMAGE_COLUMNS={
MediaStore.Images.Media.DATA,//图片路径
MediaStore.Images.Media.DISPLAY_NAME,//显示的名字
MediaStore.Images.Media.DATE_ADDED,//添加时间
MediaStore.Images.Media.MIME_TYPE,//图片扩展类型
MediaStore.Images.Media.SIZE,//图片大小
MediaStore.Images.Media._ID,//图片id
};
@Override
public Loader<Cursor> onCreateLoader(int id, Bundle args) {
toggleShowLoading(true,getString(R.string.common_loading));
CursorLoader cursorLoader = new CursorLoader(ImageSelectActivity.this, MediaStore.Images.Media.EXTERNAL_CONTENT_URI,IMAGE_COLUMNS,
IMAGE_COLUMNS[4] + " > 0 AND "+IMAGE_COLUMNS[3] + " =? OR " +IMAGE_COLUMNS[3] + " =? ",
new String[]{"image/jpeg","image/png"},IMAGE_COLUMNS[2] + " DESC");
return cursorLoader;
}
@Override
public void onLoadFinished(Loader<Cursor> loader, Cursor data) {
if(data != null && data.getCount() > 0){
ArrayList<String> imageList = new ArrayList<>();
if(mShowCamera){
imageList.add("");
}
while (data.moveToNext()){
String path = data.getString(data.getColumnIndexOrThrow(IMAGE_COLUMNS[0]));
imageList.add(path);
Log.e("ImageSelect", "IIIIIIIIIIIIIIIIIIII=====>"+path);
}
//显示数据
showListData(imageList);
toggleShowLoading(false,getString(R.string.common_loading));
}
}
@Override
public void onLoaderReset(Loader<Cursor> loader) {
}
5.ThreadPool （线程池）
把任务分解成不同的单元，分发到各个不同的线程上，进行同时并发处理。
线程池适合用在把任务进行分解，并发进行执行的场景。
系统提供ThreadPoolExecutor帮助类来帮助我们简化实现线程池。
使用线程池需要注意的问题:
使用线程池需要特别注意同时并发线程数量的控制，理论上来说，我们可以设置任意你想要的并发数量，但是这样做非常的不好。因为CPU只能同时执行固定数量的线程数，一旦同时并发的线程数量超过CPU能够同时执行的阈值，CPU就需要花费精力来判断到底哪些线程的优先级比较高，需要在不同的线程之间进行调度切换。
一旦同时并发的线程数量达到一定的量级，这个时候CPU在不同线程之间进行调度的时间就可能过长，反而导致性能严重下降。另外需要关注的一点是，每开一个新的线程，都会耗费至少64K+的内存。为了能够方便的对线程数量进行控制，ThreadPoolExecutor为我们提供了初始化的并发线程数量，以及最大的并发数量进行设置。
Executors类中几种线程池，有哪些缺点：
newFixedThreadPool 和 newSingleThreadExecutor:主要问题是堆积的请求处理队列可能会耗费非常大的内存，甚至 OOM。
newCachedThreadPool 和 newScheduledThreadPool:主要问题是线程数最大数是 Integer.MAX_VALUE，可能会创建数量非常多的线程，甚至 OOM
什么是内存泄漏？
当一个对象已经不需要在使用了，本应该被回收，而另一个正在使用的对象持有它的引用，导致对象不能被回收。因为不能被及时回收的本该被回收的内存，就产生了内存泄漏。如果内存泄漏太多会导致程序没有办法申请内存，最后出现内存溢出的错误。
android中导致内存泄漏的只要几个点？
1.使用匿名内部类
以线程为例，当Activity调用了createNonStaticInnerClass方法，然后退出当前Activity时，因为线程还在后台执行且当前线程持有Activity引用，只有等到线程执行完毕，Activitiy才能得到释放，导致内存泄漏。
常用的解决方法有很多，第一把线程类声明为静态的类，如果要用到Activity对象，那么就作为参数传入且为WeakReference,第二在Activity的onDestroy时，停止线程的执行。
实例代码如下：
/**
* 非静态内部类
*/
public void createNonStaticInnerClass(){
CustomThread mCustomThread = new CustomThread();
mCustomThread.start();
}
public class CustomThread extends Thread{
@Override
public void run() {
super.run();
while (true){
try {
Thread.sleep(5000);
Log.i(TAG,"CustomThread ------- 打印");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
解决方案的代码：
public static class CustomThread extends Thread{
private WeakReference<MainActivity> mActivity;
public CustomThread(MainActivity activity){
mActivity = new WeakReference<MainActivity>(activity)
}
}
2.使用异步事件处理机制Handler
这个应该是我们平时使用最多的一种方式，如果当handler中处理的是耗时操作，或者当前消息队列中消息很多时，那当Activity退出时，当前message中持有handler的引用，handler又持有Activity的引用，导致Activity不能及时的释放，引起内存泄漏的问题。
解决handler引起的内存泄漏问题常用的两种方式：
a)通过静态的内部类实现，对外部的activity弱引用化
b)在onDestroy中调用mHandler.removeCallbacksAndMessages(null)
3.使用静态变量
静态变量引用了activity的实例或activity的上下文
4.资源未关闭
常见的就是数据库游标没有关闭，对象文件流没有关闭
5.设置监听
常见的是在观察者模式中出现，我们在退出Acviity时没有取消监听，导致被观察者还持有当前Activity的引用，从而引起内存泄漏。
常见的解决方法就是在onPause中注消监听
6.使用AsyncTask
匿名内部类持有外部类的引用，AsyncTask耗时操作导致Activity不能及时释放，引起内存泄漏。
解决方法:
1.声明为静态类，
2.在onPause中取消任务
7.使用Bitmap
我们知道当bitmap对象没有被使用(引用)，gc会回收bitmap的占用内存，当时这边的内存指的是java层的，那么本地内存的释放呢？
我们可以通过调用bitmap.recycle()来释放C层上的内存，防止本地内存泄漏
8.使用单例模式
实例代码：
private static ComonUtil mInstance = null;
private Context mContext = null;
public ComonUtil(Context context) {
mContext = context;
}
public static ComonUtil getInstance(Context context) {
if (mInstance == null) {
mInstance = new ComonUtil(context);
}
return mInstance;
}
我们平时使用的单例模式，当然这里暂时没有考虑线程安全。当我们传递进来的是Context，那么当前对象就会持有第一次实例化的Context，如果Context是Activity对象，
那么就会产生内存泄漏。因为当前对象ComonUtil是静态的，生命周期和应用是一样的，只有应用退出才会释放，导致Activity不能及时释放，带来内存泄漏。
解决方法：
传入Application的上下文
什么是内存抖动？
堆内存都有一定的大小，能容纳的数据是有限制的，当Java堆的大小太大时，垃圾收集会启动停止堆中不再应用的对象，来释放内存。当在极短时间内分配给对象和回收对象的过程就是内存抖动。
产生内存抖动的原因？
从术语上来讲就是极短时间内分配给对象和回收对象的过程。
一般多是在循环语句中创建临时对象，在绘制时配置大量对象或者执行动画时创建大量临时对象
内存抖动会带来UI的卡顿，因为大量的对象创建，会很快消耗剩余内存，导致GC回收，GC会占用大量的帧绘制时间，从而导致UI卡顿，关于UI卡顿会在后面章节讲到。
android中4种引用
1.StrongReference强引用——从不被回收，java虚拟机停止时，才终止
2.SoftReference软引用——当内存不足时，会主动回收，使用SoftReference使用结合ReferenceQueue构造有效期短
3.WeakReference弱引用——每次垃圾回收时，被回收
4.PhatomReference虚引用——每次垃圾回收时，被回收.结合ReferenceQueue来跟踪对象被垃圾回收器回收的活动
网友评论