二分查找
在android的SparseArray中get方法就是通过二分法查找到结果。
二分查找的前提是有一个已经排好序的数组。
二分查找
思路：假设我们需要查找22这个值在数组中的位置，如上图的数组，取数组的中间下标5中的值，为21，用目标值22跟21做对比，22大于21，就在右边继续查找22这个值，否则在左边查找。
接着再从剩下的数组大小中同理取一半的下标为8，值是62同目标22对比大于22，这在右边查找。以此类推，直到找到目标22为止，返回22的下标。没找到返回负 1。
public void Test(){
int[] array = {4,7,8,10,14,21,22,36,62,77,81,91};
int key = 22;
System.out.println(binarySearch(array,0,array.length,key));
}
/**
* 在array中从start到end查找有没有key这个值
* @param array
* @param start
* @param end
* @param key
*/
private int binarySearch(int[] array,int start,int end,int key){
int lo = 0;
int low = start;
int hight = end -1;
while (low < hight){
int mid = (low + hight)>>>1;
int midVal = array[mid];
if (midVal <key){
low = mid +1;
}else if (midVal > key){
hight = mid -1;
}else {
return mid;
}
}
return ~lo;
}
输出结果就是 6
也有使用递归的思想去实现二分查找，但不建议这样做。
/**
* 递归实现二分查找
* @param array
* @param start
* @param end
* @param key
* @return
*/
private int binarySearch2(int[] array,int start,int end,int key){
int mid = (start+end)>>>1;
if (array[mid] == key){
return mid;
}
if (start <end){
if (array[mid] < key){
return binarySearch2(array,mid + 1,end,key);
}else if (array[mid] > key){
return binarySearch2(array,start,mid - 1,key);
}
}
return 0;
}
快速排序
应用场景：大量数据并且是线性结构。
短处：
1、有大量重复数据，性能不好。
2、单向链式结构处理性能不好（一般来说，链式都不使用）
排序排序的思想：
给一组数据进行排序，首先把左边第一个值暂存在T上。
在数组两端各定义一个指针(就叫指针吧，好理解)。
移动high指针取值，然后跟T中存的数据比对(这里是31)。
如果high指针取的值(12)比暂存的值(31)小。
就替换low指针指向的值。
接着换low指针移动跟暂存的值(31)做对比。
如果low指向的值(68)比暂存值(31)大。
就把high指向的值替换为low的值。
接着再次更换移动的指针为high。
同样的指针指向的值(23)比暂存值(31)小，就替换。
用high指针的值替换low指针的值。
同理，再次切换指针移动，比暂存值大就往high指针替换，比暂存值小就往low指针替换。
最后两个指针指到了同一个值上。
把暂存值替换上去。
这样第一轮的排序完成，31左边的都比它小，右边的都比它大。
然后排序左边和右边，实现整个数组的排序。
public void testQuickSort(){
int[] array = new int[]{31,68,45,90,23,39,54,12,87,76};
quickSort(array,0,array.length-1);
for (int i = 0;i<array.length;i++){
System.out.print(array[i]+" ");
}
}
private void quickSort(int[] array,int begin,int end){
if ((end - begin)<=0) return;
int x = array[begin];
int low = begin;
int high = end;
//由于会从两个方向取数据，需要定义一个方向；
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;
}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;
//开始完成左右两边的操作
quickSort(array,begin,low-1);
quickSort(array,low+1,end);
}
归并排序
思想：
应用场景：数据量大并且是链式结构。
短处：需要空间大。
public static void mergeSort(int[] array, int left, int right) {
if (left == right) {
return;
} else {
int mid = (left + right) >>> 1;
mergeSort(array, left, mid);//排好左边 L
mergeSort(array, mid + 1, right);//排好右边 R
merge(array, left, mid + 1, right);//再对左右进行合并 D
}
}
//归并排序
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++];
} else {
array[k++] = rightArray[j++];
}
}
while (i < leftSize) {
//左边还有数据没用完
array[k++] = leftArray[i++];
}
while (j < rightSize) {
//右边还有数据没用完
System.out.print("k：" + k);
System.out.print("length：" + array.length);
array[k++] = rightArray[j++];
}
}
