二分查找
我们平时用的for循环，挨个去查询数组集合里的值是否符合要求，是属于顺序查找。
如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。
如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。
但是顺序查找有个缺点，就是当数据量很大的时候，查找一个靠近中间或后面的数据，就会很耗时。打个比方，如果你有1W个数据，你要查找的的数据在最后一个，那么你用顺序查找要执行1W个查找比对的方法才能给数据查出来，这样相当的费时费力。
二分查找：从数组集合中间的位置开始查找。如果查找数据比目标数据小，则取前半部分数据继续进行二分查找。反之同样。
前题条件：数据已经排序
注意：设计成左闭右开 [0,count) --是一种区间无重复的思想
random(０，１)等大量的数学函数
for(int i=0;i<array.length;i++）
/**
* 二分查找 前题条件：数据已经排序过
*
* @param arr
* @param fromIndex
* @param toIndex
* @param key
* @return
*/
public static int sort_binary_search(int[] array, int fromIndex,
int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) / 2;// 取中间
int midVal = array[mid];
if (key > midVal) {// 去右边找
low = mid + 1;
} else if (key < midVal) {// 去左边找
high = mid - 1;
} else {
return mid;
}
}
return -(low + 1);// low+1表示找不到时停在了第low+1个元素的位置
}
快速排序 （前序）
我们之前介绍过冒泡排序和选择排序，适合3-5个数据的排序情况。
快速排序的可以应用于 数据量大并且是线性结构的集合排序情况。
原理：
1.取数组的其中一个数据n，（一般都是第一个）
2.记录低位位置low,和高位位置high;
3.取high位的数据 h和n对比,如果h>n,high=high-1;h<n, h放在low位置，并且 low = low+1, 取low位数据 l 和 n对比， 如果 l<n,low = low+1; l>n,l放在high位置，high = high -1,去high位数据h1和n对比....
4.low== high时，n放在low位，这一轮比较下来，n的左边都是比自己小的,右边都是比自己大的;
对左边的数据 执行1,2,3,4,5； 对右边的数据执行1,2,3,4,5
image.png
短处
有大量重复数据的时候，性能不好
单向链式结构处理性能不好（一般来说，链式都不使用）
/**
* 快速排序
*
* @param array
* @param begin
* @param end
*/
public static void sort_quick(int[] array, int begin, int end) {
if (end - begin <= 0)
return;
int x = array[begin];
int low = begin;// 0
int high = end;// 5
// 由于会从两头取数据，需要一个方向
boolean direction = true;
L1: while (low < high) {
if (direction) {// 从右往左找
for (int i = high; i > low; i--) {
if (array[i] <= x) {
array[low++] = array[i];
high = i;
direction = !direction;
continue L1;
}
}
high = low;// 如果上面的if从未进入，让两个指针重合
} else {
for (int i = low; i < high; i++) {
if (array[i] >= x) {
array[high--] = array[i];
low = i;
direction = !direction;
continue L1;
}
}
low = high;
}
}
// 把最后找到的值 放入中间位置
array[low] = x;
// 开始完成左右两边的操作
sort_quick(array, begin, low - 1);
sort_quick(array, low + 1, end);
}
归并排序（后序）
左边的数组和右边的数组都要是有序的
应用场景
数据量大并且有很多重复数据，链式结构
短处
需要空间大（用空间换时间）
/**
* 归并排序
* @param array
* @param left
* @param right
*/
public static void sort_merge(int array[],int left,int right){
if(left==right){
return;
}else{
int mid=(left+right)/2;
sort_merge(array,left,mid);
sort_merge(array,mid+1,right);
merge(array,left,mid+1,right);
}
}
// 0 4 7
// 1 2 5 9 3 4 10 11
public static void merge(int[] array,int left,int mid,int right){
int leftSize=mid-left;
int rightSize=right-mid+1;
//生成数组
int[] leftArray=new int[leftSize];
int[] rightArray=new int[rightSize];
//填充数据
for(int i=left;i<mid;i++){
leftArray[i-left]=array[i];
}
for(int i=mid;i<=right;i++){
rightArray[i-mid]=array[i];
}
//合并
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArray[i]<rightArray[j]){
array[k]=leftArray[i];
k++;i++;
}else{
array[k]=rightArray[j];
k++;j++;
}
}
while(i<leftSize){
array[k]=leftArray[i];
k++;i++;
}
while(j<rightSize){
array[k]=rightArray[j];
k++;j++;
}
}
