# 算法
# 基本查找
public class FindText {
public static void main(String[] args) {
//基本查找
//需求：定义一个方法利用基本查找，查询某个数据是否存在
int[] arr = {1, 2, 3, 4, 5, 5, 7, 8, 9, 10};
System.out.println(myFind(arr, 11));//false
System.out.println(myFind(arr, 1));//true
//使用基本查找 找出元素索引，可能具有重复元素
System.out.println(myFindRepeat(arr, 5));//[4, 5]
}
//基本查找
private static Boolean myFind(int[] arr, int num) {
for (int item : arr)
if (item == num) return true;
return false;
}
//使用基本查找 找出元素索引，可能具有重复元素
private static ArrayList<Integer> myFindRepeat(int[] arr, int num) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == num) list.add(i);
}
return list;
}
}
# 二分查找
package algorithm;
import java.util.ArrayList;
public class FindText {
public static void main(String[] args) {
//二分查找
//二分查找的前提：数组中的数据必须是有序的
//核心逻辑：排除掉一半的查找范围
System.out.println("二分查找结果" + binarySearch(arr, 10));//9
System.out.println("二分查找结果" + binarySearch(arr, 11));//-1
}
//二分查找
private static int binarySearch(int[] arr, int num) {
//小索引
int left = 0;
//大索引
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == num) return mid;
else {
if (num > arr[mid])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
}
# 冒泡排序
规则：把相邻的数据两两比较，小的放前面，大的放后面
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1, 5, 3, 9, 2, 7, 4, 6, 8};
int[] result = mySort(arr);
System.out.println(Arrays.toString(result));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
private static int[] mySort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int j = 0;
//内循环 每一轮中比较数据 寻找最大值
//-1 防止索引越界
//-i 提高效率
while (j < arr.length - 1 - i) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
j++;
}
}
return arr;
}
}
# 选择排序
规则：从索引0开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面，以此类推
public class SelectSort {
public static void main(String[] args) {
//选择排序
//规则：从索引0开始，拿着每一个索引上的元素跟后面的元素依次比较，小的放前面，大的放后面，以此类推
int[] result1 = mySort1(arr);
System.out.println(Arrays.toString(result1));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
private static int[] mySort1(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//拿着i跟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;
}
}
}
return arr;
}
}
# 插入排序
- 将0索引的元素到n索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。
- 遍历无序的数据，将遍历到的元素插入有序序列中的合适位置，如遇到相同数据，插在后面。
- N的范围：0~最大索引
public class InsertSort {
public static void main(String[] args) {
//插入排序
int[] result2 = mySort2(arr);
System.out.println(Arrays.toString(result2));//[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
private static int[] mySort2(int[] arr) {
//克隆数组
int[] arrClone = arr.clone();
//1.找到无序的那一组是从哪个索引开始的
int startIndex = -1;
for (int i = 0; i < arrClone.length - 1; i++) {
if (arrClone[i] > arrClone[i + 1]) {
startIndex = i + 1;//找到无序的那一组的开始索引
break;
}
}
//遍历无序的列表
for (int i = startIndex; i < arrClone.length; i++) {
//记录当前要插入数据的索引
int j = i;
//将当前数据倒着插入到有序的列表中
while (j > 0 && arrClone[j] < arrClone[j - 1]) {
//交换位置(与前面的数据进行交换)
int temp = arrClone[j];
arrClone[j] = arrClone[j - 1];
arrClone[j - 1] = temp;
j--;
}
}
return arrClone;
}
}
# 递归算法
递归算法：就是方法中调用方法本身的现象(自己调用自己)
注意
递归一定要有出口，否则就会出现内存溢出
# 书写递归的两个核心
- 找出口：什么时候不在调用此方法
- 找规则：如何把大问题变成规模较小的问题
- 方法内部再次调用方法的时候要更靠近出口
public class Recursion {
public static void main(String[] args) {
//递归求和
int start = 1;
int end = 100;
int sum = mySum(start, end);
System.out.println(start + "到" + end + "之间的和为：" + sum);//5050
//递归求阶乘
int result3 = myFactorial(5);
System.out.println("阶乘为：" + result3);//120
}
//递归求阶乘
private static int myFactorial(int i) {
if (i == 1) return 1;
else return i * myFactorial(i - 1);
}
//递归求和
private static int mySum(int start, int end) {
if (start == end)
return start;
else return start + mySum(start + 1, end);
}
}
# 快速排序
快速排序用时非常快，在测试排序十万随机数时，快速排序比其他排序算法快了20倍
冒泡排序时间:19046
选择排序时间:15612
插入排序时间:1754
快速排序时间:20
第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置
结束后比基准数小的全部在左边，比基准数大的全部在右边
public class QuickSort {
public static void main(String[] args) {
//快速排序
//第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置
// 结束后比基准数小的全部在左边，比基准数大的全部在右边
int[] result4 = myQuickSort3(arr.clone(), 0, arr.length - 1);
System.out.println(Arrays.toString(result4));
}
//快速排序
private static int[] myQuickSort3(int[] arr, int i, int j) {
int start = i;
int end = j;
//递归的出口
if (start > end) return arr;
//1.记录基准数
int base = arr[i];
//2.利用循环找到要交换的数字
while (start != end) {
//3.利用end，从后往前开始找，找比基准数小的数字
while (start < end && arr[end] >= base) {
//左边找到比基准数大的数字
end--;
}
//4.利用start找到比基准数大的数字
while (start < end && arr[start] <= base) {
start++;
}
//5.交换start和end找到的数字
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
//当start和end都指向一个元素的时候，那么上面的循环就会结束
//表示已经找到了基准数在数组中应该存入的位置
//基准数归位
//就是拿着这个范围中的第一个数字，跟start指向的元素进行交换
int temp = arr[i];
arr[i] = arr[start];
arr[start] = temp;
//确定基准数左边的位置 重复刚刚的事情
myQuickSort3(arr, i, start - 1);
//确定基准数右边的位置 重复刚刚的事情
myQuickSort3(arr, end + 1, j);
return arr;
}
}
# 操作数组的工具类Arrays
| 方法 | 描述 |
|---|---|
public static String toString(int[] a) | 将数组转换为字符串表示形式。 |
public static int binarySearch(int[] a, int key) | 二分查找法查找元素 |
public static void fill(int[] a, int val) | 使用指定的值填充数组 |
public static int[] copyOf(int[] original, int newLength) | 创建一个新的数组 |
public static int[] copyOfRange(int[] original, int from, int to) | 创建一个新的数组(指定范围) |
public static void sort(int[] a) | 按照默认方式对数组进行排序。 |
public static void sort(int[] a, 排序规则) | 按照指定的规则进行排序 |