二分搜索
常用的两个东西，排序和查找，现在就是来主要说说查找中的一种二分搜索和排序中的一种快速排序
一、何为二分搜索？
二分搜索是通过持续跟踪排好序的数组中包含元素t的范围（前提是数组中一定存在元素t，并且数组是已经排序的数组）来解决问题
搜索的一开始范围是整个数组，然后通过将t与数组中的中间项进行比较，如果t大于中间项，就在大于中间项的范围再次折中寻找
如果t小于中间项就在小于中间项的范围再次折中寻找
二、二分搜索的关键思想是如果t在x[0...n-1]的数组中，那么它就一定存在与x中的上特定位置
三、代码实现
/**
* array 待被查询的shuz
* num 要查询的元素
* lower 对应的查找下限
* upper 对应的查找上限
*/
public class erfenchazhao {
public static int arrServet(int[] array,int num){
int lower = 0;
int upper = array.length-1;
while (lower<=upper){
// 取中间项
int middle = (lower+upper) / 2;
if(num == array[middle]){
return middle;
}else if(num < array[middle]){
upper = middle -1;
}else{
lower = middle +1;
}
}
return -1;
}
public static void main(String[] ages){
int[] arr =new int[]{1,2,4,6,8,9,20,52,65,72};
System.out.println(arrServet(arr,20));
}
}
快速排序
一、快速排序的基本思路
拿到一个无序的数组以后，首先定义一个数组中的中轴数，然后把数组中小于中轴数的数据放到左边，把大于中轴数的数据放在右边，然后在用递归分治的方式分别对两边的数据进行排序
二、代码实现
/**
* 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
*
* @param numbers 带查找数组
* @param low 开始位置
* @param high 结束位置
* @return 中轴所在位置
*/
public static int getMiddle(int[] numbers,int low,int high){
int temp = numbers[low]; //数组的第一个作为中轴
while (low<high){
while (low<high && numbers[high]>temp){
high--;
}
numbers[low] = numbers[high];//比中轴小的记录移到低端
while (low<high && numbers[low]<temp){
low++;
}
numbers[high] = numbers[low];//比中轴大的记录移到高端
}
numbers[low] = temp;//中轴记录到尾端
return low;
}
//递归形式的分治排序算法
/**
*
* @param numbers 待排序的数组
* @param low 开始位置
* @param high 结束位置
*/
public static void quickSort(int[] numbers,int low,int high){
if(low<high){
int middle = getMiddle(numbers,low,high);//将数组进行一分为二
quickSort(numbers,low,middle-1);//对低于中轴字段进行排序
quickSort(numbers,middle+1,high);//对高与中轴字段进行排序
}
}
// 快速排序提供方法调用
public static void quick(int[] numbers){
if(numbers.length>0){
//查看数组是否为空
quickSort(numbers,0,numbers.length-1);
}
}
//打印数组的函数
public static void printArr(int[] numbers){
for(int i = 0;i<numbers.length;i++){
System.out.println(numbers[i]+",");
}
}
public static void main(String[] args){
int[] numbers = {20,10,5,9,7,36,-2};
quick(numbers);
System.out.println("快速排序后");
printArr(numbers);
}
}
通常情况下排序和查找都是组合使用，排好序的数据结构对查询的帮助也是很大的
