赞
踩
package io.xiaoduo.arithmetic; public class Test1 { public static void main(String[] args) { int[] arr = {1, 12, 24, 35, 43, 52, 64, 75, 87, 99, 100}; System.out.println(binarySearch(arr, 75)); // 7 } // 二分查找 private static int binarySearch(int[] arr, int num) { int min = 0; int max = arr.length - 1; while (true) { if (min > max) { return -1; } int mid = (min + max) / 2; if (arr[mid] > num) { max = mid - 1; } else if (arr[mid] < num) { min = mid + 1; } else { return mid; } } } }
总结
二分查找改进/插值查找
二分查找改进/斐波那契查找
package io.xiaoduo.arithmetic; public class Test2 { public static void main(String[] args) { // 分块查找 int[] arr = {7, 10, 13, 19, 16, 20, 27, 22, 30, 40, 36, 43, 50, 48}; // 第一步分块 Block b1 = new Block(10, 0, 1); Block b2 = new Block(20, 2, 5); Block b3 = new Block(40, 6, 10); Block b4 = new Block(50, 11, 13); Block[] blockArr = {b1, b2, b3, b4}; // 要查找的元素 int num = 20; // 分块查找算法函数 int index = blockSearch(blockArr, arr, num); System.out.println(index); } private static int blockSearch(Block[] blockArr, int[] arr, int num) { // 找到num属于哪个块 int indexBlock = findIndexBlock(blockArr, num); // 超出块的范围 if (indexBlock == -1) return -1; // 获取该块的开始和结束素引 int startIndex = blockArr[indexBlock].getStartIndex(); int endIndex = blockArr[indexBlock].getEndIndex(); for (int i = startIndex; i <= endIndex; i++) { if (arr[i] == num) { return i; } } return -1; } private static int findIndexBlock(Block[] blockArr, int num) { for (int i = 0; i < blockArr.length; i++) { int max = blockArr[i].getMax(); if (num <= max) { return i; } } return -1; } } class Block { public int max; public int startIndex; public int endIndex; public Block() { } public Block(int max, int startIndex, int endIndex) { this.max = max; this.startIndex = startIndex; this.endIndex = endIndex; } public String toString() { return "Block{}"; } /** * 获取 * * @return max */ public int getMax() { return max; } /** * 设置 * * @param max */ public void setMax(int max) { this.max = max; } /** * 获取 * * @return startIndex */ public int getStartIndex() { return startIndex; } /** * 设置 * * @param startIndex */ public void setStartIndex(int startIndex) { this.startIndex = startIndex; } /** * 获取 * * @return endIndex */ public int getEndIndex() { return endIndex; } /** * 设置 * * @param endIndex */ public void setEndIndex(int endIndex) { this.endIndex = endIndex; } }
扩展的分块查找(无规律的数据)
扩展的分块查找(查找时添加数据),可以使用哈希查找
总结
package io.xiaoduo.arithmetic; public class Test3 { public static void main(String[] args) { // 冒泡排序 int[] arr = {2, 1, 6, 4, 7, 3, 8, 5, 9}; mySort(arr); for (int i : arr) { System.out.print(i + " "); } } private static void mySort(int[] arr) { for (int i = 0; i < arr.length; 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; } } } } }
package io.xiaoduo.arithmetic; public class Test4 { public static void main(String[] args) { // 选择排序 int[] arr = {2, 1, 6, 4, 7, 3, 8, 5, 9, 13, 10, 12, 11}; mySort(arr); for (int i : arr) { System.out.print(i + " "); } } private static void mySort(int[] arr) { 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; } } } } }
package io.xiaoduo.arithmetic; public class Test5 { public static void main(String[] args) { // 插入排序 int[] arr = {2, 1, 6, 4, 7, 3, 8, 5, 9, 13, 10, 12, 11}; mySort(arr); } private static void mySort(int[] arr) { int startIndex = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] > arr[i + 1]) { startIndex = i + 1; break; } } System.out.println(startIndex); for (int i = startIndex; i < arr.length; i++) { int j = i; while (j > 0 && arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; j--; } } for (int i : arr) { System.out.print(i + " "); } } }
package io.xiaoduo.arithmetic; import java.util.Random; public class Test6 { public static void main(String[] args) { // 快速排序 // int[] arr = {7, 2, 1, 6, 4, 3, 8, 5, 9, 13, 10, 12, 11}; int[] arr = new int[1000000]; Random r = new Random(); for (int i = 0; i < arr.length; i++) { arr[i] = r.nextInt(); } long start = System.currentTimeMillis(); quickSort(arr, 0, arr.length - 1); long end = System.currentTimeMillis(); System.out.println(end - start); // for (int i : arr) { // System.out.print(i + " "); // } } private static void quickSort(int[] arr, int i, int j) { // 开始索引 int start = i; // 结束素引 int end = j; if (start > end) { return; } // 基准数 int baseNumber = arr[i]; while (start != end) { while (true) { if (end <= start || arr[end] < baseNumber) { break; } end--; } while (true) { if (end <= start || arr[start] > baseNumber) { break; } start++; } int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; } int temp = arr[i]; arr[i] = arr[start]; arr[start] = temp; quickSort(arr, i, start - 1); quickSort(arr, start + 1, j); } }
方法名 | 说明 |
---|---|
public static String toString(数组) | 把数组拼接成一个字符串 |
public static int binarySearch(数组,查找的元素) | 二分查找法查找元素 |
public static int[] copyOf(原数组,新数组长度) | 拷贝数组 |
public static int[] copyOfRange(原数组,起始索引,结束索引) | 范围拷贝数组 |
public static void fill(数组,元素) | 填充数组 |
public static void sort(数组) | 按照默认方式进行排序 |
public static void sort(数组,排序规则) | 按照指定规则排序 |
Lambda表达式是JDK8开始后的一种新语法形式
例如 ( ) -> {}
Arrays.sort(arr, (Integer o1, Integer o2) -> {
return o2 - o1;
});
Lambda表达式可以用来简化匿名内部类的书写
Lambda表达式只能简化函数式接口的匿名内部类的写法
函数式接口:有且仅有一个抽象方法的接口叫做函数式接口,接口上方可以加@FunctionalInterface注解
和 js 的箭头函数写法很像,省略写法和箭头函数一样
s1.compareTo(s2)
返回int,-1表示s1小于s2, 遍历字符串ascall码表依次比较Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。