JAVA 常见算法（选择排序，二分查找）
JAVA 常见算法（选择排序，二分查找）
选择排序
选择排序的思想
- 每轮选择当前位置，开始找出后面的较小值与该位置交换
选择排序的关键
- 确定总共需要选择几轮：数组的长度-1
- 控制每轮从以前位置为基准，与后面元素选择几次
二分查找
- 二分查找性能好，二分查找的前提是必须是排好序的数据
总结
- 数组的二分查找的实现步骤是怎样的？
- 定义变量记录左边和右边位置
- 使用while循环控制查询（条件是左边位置<=右边位置）
- 循环内部获取中间索引
- 判断当前要找的元素如果大于中间元素，左边位置=中间位置+1
- 判断当前要找的元素如果小于中间元素，右边位置=中间位置-1
- 判断当前要找的元素如果等于中间元素，返回当前中间元素索引
使用实例
import java.util.Arrays;
public class ArraysDemo {
//目标：掌握快排与二分查找算法
public static void main(String[] args) {
int[] arr = new int[]{130, 39, 56, 43, 78, 98, 1};
int[] arr1 = new int[]{130, 39, 56, 43, 78, 98, 1};
fastSort(arr);
bulletSort(arr1);
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(arr1));
System.out.println(binarySearch(arr, 43));
}
/**
*二分查找算法
* @param arr 源数组
* @param date 需要查找的数据
* @return 若数组中存在相应数据则返回对应索引，否则返回 -（应插入位置+1）
*/
public static int binarySearch(int[] arr, int date){
//定义左右索引
int left = 0;
int right = arr.length-1;
//开始循环，进行二分查找
while(left<=right){
int middle = (left+right)/2;
if(date>arr[middle]){
//往右边查找
left = middle + 1;
}else if(date<arr[middle]){
//往左边查找
right = middle-1;
}else{
return middle;
}
}
return -(arr.length+1);
}
/**
* 选择排序算法
* @param arr 源数组
*/
public static void fastSort(int[] arr){
/*
* i=0, j=1,2,....,arr.length-1
* i=1, j=2,3,...,arr.length-1
* ...
* i=arr.length-2 j=arr.length-1
* */
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
if (arr[i]>arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
/**
* 冒泡拍寻
* @param arr 源数组
*/
public static void bulletSort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-(i+1); j++) {
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}