本文目录一览：
java线性查找算法的平均次数为什么是n/2
平均次数是(n+1)/2，不是n/2。
被查找的数是第1个数，则需用第1个数和被查找的数比较，要比较1次。
被查找的数是第2个数，则需用第1个数、第2个数和被查找的数比较，要比较2次。
...
被查找的数是第n个数，则需用第1个数、第2个数、...、第n个数和被查找的数比较，要比较n次。
平均次数为(1+2+...+n)/n=(n+1)/2。
常见查找和排序算法
查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。
改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。
适用条件：
二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。
循环实现
递归实现
待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。
归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。
归并方法将数组中两个已经排序的部分归并成一个。
将一个大数组分成两个小数组去求解。
因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。
先归并那些微型数组，然后成对归并得到的微型数组。
取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 大的元素。
该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。
堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。
堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。
在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。
类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。
将新元素放到数组末尾，然后上浮到合适的位置。
从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。
一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。
对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。
当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。
实间复杂度N*K
快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。
java 线性查找和二分查找的区别
一 线性查找
定义：在一列给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。
线性查找又称为顺序查找。如果查找池是某种类型的一个表，比如一个数组，简单的查找方法是从表头开始，一次将每一个值与目标元素进行比较。最后，或者查找到目标，或者达到表尾，而目标不存在于组中，这个方法称为线性查找。
二 折半查找
定义：二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））
折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果xa[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果xa[n/2]，则我们只要在数组a的右 半部继续搜索x。
java中的散列码
首先，你要弄明白原因，你要明白两点：
1、你得有一定的汇编功底，了解堆和栈关系。
2、你得明白，java对像类和封装类在内存是怎么存储的。
1首先解答为什么(a == b)－"不相等"
对像类和封装类，在内存中这样存储的：
a.当new一个对像类时，就会在堆中开辟一块空间，然后，会把这个空间的地指向你new 的这个句柄，这个句柄就会放在栈中，（栈）就像个列表，CPU会向栈发送指令进行操作。（栈像一本书的目录，堆像书中的详细章节）栈中存放的对像的具体物理地址。
== ：比的是栈中的东西，a栈的内容是c8（散列码是不分正负的，内存表是1－－－11001000）
b栈的容易是c8（就是数字200的16进制，内存表是0－－－11001000）
因为（1－－－11001000）！＝（0－－－11001000）所以在堆中要分两段存储，比如堆地址为
00001000存放（1－－－11001000）为a，
堆地址为
00002000存放（0－－－11001000）为b,==比较的是00001000和00002000，所以不想等。
(String是比较特殊的对像，不是基本类型)
如果：String c = "abc";
String d = "abc";
它没有new 在定义d = "abc";的时候，因为堆中已经有"abc"了就直接把它的地址负给了d，所以
c和d的栈中存储的都是"abc"在堆中二进制地址码。所以不管是c==d还是c.equals(d)都是相等的。
equals:比较的是栈地址指向的堆中的内容是否想等。针对所有对像都有效。
比较的是（1－－－11001000）和（0－－－11001000）所表示的内容c8，所以想等。
这是有点不太好说清楚，不知道你明白了没有。
