1 直接插入排序（稳定的排序） 我们经常会到这样一类排序问题：把新的数据插入到已经排好的数据列中。将第一个数和第二个数排序，然后构成一个有序序列将第三个数插入进去，构成一个新的有序序列。对第四个数、第五个数……直到最后一个数，重复第二步。 如题所示：
代码实现原理： 首先设定插入次数，即循环次数，for(int i=1;i<length;i++)，1个数的那次不用插入。 设定插入数和得到已经排好序列的最后一个数的位数。insertNum和j=i-1。 从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。 将当前数放置到空着的位置，即j+1。
public static void insterto() { int > a[]={2,38,65,97,76,13,27,49,78,34,12,64,5,4, > 62,99,98,54,56,17,18,23,34,15,35,25,53,51}; > int temp=0; > for(int i=1;i<a.length;i++){ > temp=a[i]; > int j=i-1; > for(;j>=0&&temp<a[j];j--){ > a[j+1]=a[j]; //将大于temp的值整体后移一个单位 > } > a[j+1]=temp; > } > for(int i=0;i<a.length;i++) { > System.out.print(a[i]+"\t"); } > }2 希尔排序（非稳定排序算法） 针对直接插入排序的下效率问题，有人对次进行了改进与升级，这就是现在的希尔排序。希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
如图所示：
对于直接插入排序问题，数据量巨大时。 将数的个数设为n，取奇数k=n/2，将下标差值为k的数分为一组，构成有序序列。 再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。 重复第二步，直到k=1执行简单插入排序。
代码实现的思路： 首先确定分的组数。 然后对组中元素进行插入排序。 然后将length/2，重复1,2步，直到length=0为止。
3 简单选择排序（稳定）
常用于取序列中最大最小的几个数时。 (如果每次比较都交换，那么就是交换排序；如果每次比较完一个循环再交换，就是简单选择排序。) 遍历整个序列，将最小的数放在最前面。 遍历剩下的序列，将最小的数放在最前面。 重复第二步，直到只剩下一个数。
代码实现原理： 首先确定循环次数，并且记住当前数字和当前位置。 将当前位置后面所有的数与当前数字进行对比，小数赋值给key，并记住小数的位置。 比对完成后，将最小的值与第一个数的值交换。 重复2、3步。
4 堆排序（不稳定） 对简单选择排序的优化。 将序列构建成大顶堆。 将根节点与最后一个节点交换，然后断开最后一个节点。 重复第一、二步，直到所有节点断开。 交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区（有序区显示为黄色），然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置……
重复此过程：
最后，有序扩展完成即排序完成：
5 冒泡排序（稳定）
将序列中所有元素两两比较，将最大的放在最后面。 将剩余序列中所有元素两两比较，将最大的放在最后面。 重复第二步，直到只剩下一个数。
代码实现： 设置循环次数。 设置开始比较的位数，和结束的位数。 两两比较，将最小的放到前面去。 重复2、3步，直到循环次数完毕。
public static void bubble(){ int a[]={2,38,65,97,76,13,27,49,78,34,12,64,5,4, 62,99,98,54,56,17,18,23,34,15,35,25,53,51}; int len=a.length; for(int i=0;i<len;i++){ for(int j=0;j<len-i-1;j++){//注意第二重循环的条件 if(a[j]>a[j+1]){ int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } }6 快速排序（不稳定） 要求时间最快时。 选择第一个数为p，小于p的数放在左边，大于p的数放在右边。 递归的将p左边和右边的数都按照第一步进行，直到不能递归。
7 归并排序（稳定）
速度仅次于快速排序，内存少的时候使用，可以进行并行计算的时候使用。 选择相邻两个数组成一个有序序列。 选择相邻的两个有序序列组成一个有序序列。 重复第二步，直到全部组成一个有序序列。
8 基数排序（稳定） 用于大量数，很长的数进行排序时。 将所有的数的个位数取出，按照个位数进行排序，构成一个序列。 将新构成的所有的数的十位数取出，按照十位数进行排序，构成一个序列。 通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：
9总结
一、稳定性: 稳定：冒泡排序、插入排序、归并排序和基数排序 不稳定：选择排序、快速排序、希尔排序、堆排序 二、平均时间复杂度 O(n^2):直接插入排序，简单选择排序，冒泡排序。 在数据规模较小时（9W内），直接插入排序，简单选择排序差不多。当数据较大时，冒泡排序算法的时间代价最高。性能为O(n^2)的算法基本上是相邻元素进行比较，基本上都是稳定的。 O(nlogn):快速排序，归并排序，希尔排序，堆排序。 其中，快排是最好的， 其次是归并和希尔，堆排序在数据量很大时效果明显。 三、排序算法的选择 1.数据规模较小 （1）待排序列基本序的情况下，可以选择直接插入排序； （2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡 2.数据规模不是很大 （1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。 （2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序 3.数据规模很大 （1）对稳定性有求，则可考虑归并排序。 （2）对稳定性没要求，宜用堆排序 4.序列初始基本有序（正序），宜用直接插入，冒泡
各算法复杂度如下：
10查找算法 10.1顺序查找
在一有序的或者无序的数列里面，找出与给定的关键词一样的数。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。
10.2 顺序查找的优缺点
优点：代码简单易懂 缺点：当数据量大的时候，查找效率极为低下，所以该算法适合小量数据。
10.3 二分查找
1.必须采用顺序存储结构 2.必须按关键字大小有序排列。把数列分成两半进行查找，它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。
10.4 二分查找优缺点
优点是比较次数少，查找速度快，平均性能好； 其缺点是要求待查表为有序表，且插入删除困难。 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 使用条件：查找序列是顺序结构，有序。
Arrays这个类里边的查找的方法就是二分查找； Arrays中的排序使用的是调优的快速排序。
