二分查找、分块查找、冒泡排序、选择排序、插入排序、快速排序
二分查找/折半查找[*] 前提条件：数组中的数据必须是有序的
[*] 核心逻辑：每次排除一半的查找范围
[*] 优点：进步查找效率
[*] 代码
public static int binarySearch(int[] arr, int num) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (num == arr) {
// 找到
return mid;
} else if (num > arr) {
// num在mid索引的右边
start = mid + 1;
} else {
// num在mid索引的左边
end = mid - 1;
}
}
return -1;
}
分块查找
[*] 分块的原则
[*]前一块中的最大数据，小于后一块中全部的数据（块内无序，块间有序）
[*]块数数量一样寻常等于数字个数开根号。好比：16个数字一样寻常分为4块左右
[*]核心思路：先确定要查找的元素在哪一块，然后在块内挨个查找
[*] 代码
package com.gen.test;
public class BlockSearchDemo {
public static void main(String[] args) {
int[] arr = {16, 5, 9, 12, 21, 18,
32, 23, 37, 26, 45, 34,
50, 48, 61, 52, 73, 66};
// 创建3个对象
Block block1 = new Block(21, 0, 5);
Block block2 = new Block(45, 6, 11);
Block block3 = new Block(73, 12, 17);
// 定义数组管理3个块的对象（索引表）
Block[] blockArr = {block1, block2, block3};
// 获取索引
int index = getIndex(blockArr, arr, 66);
System.out.println(index);
}
/**
* 获取索引
*
* @param blockArr 索引表
* @param arr 数组
* @param num 要查找的数字
* @return 返回数字在arr中的索引，-1表示不存在
*/
private static int getIndex(Block[] blockArr, int[] arr, int num) {
// 1.先确定在哪一个块中
int indexBlock = findIndexBlock(blockArr, num);
// num比所有块的最大值要大，不存在数组中
if (indexBlock == -1) {
return -1;
}
// 2.在块中查找num
int startIndex = blockArr.getStartIndex();
int endIndex = blockArr.getEndIndex();
for (int i = startIndex; i <= endIndex; i++) {
if (num == arr) {
return i;
}
}
return -1;
}
/**
* 查找num在哪一个块中
*
* @param blockArr
* @param num
* @return 返回块索引，-1表示不存在
*/
private static int findIndexBlock(Block[] blockArr, int num) {
for (int i = 0; i < blockArr.length; i++) {
if (num <= blockArr.getMax()) {
return i;
}
}
return -1;
}
}
class Block {
// 最大值
private int max;
// 起始索引
private int startIndex;
// 结束索引
private int endIndex;
public Block() {
}
public Block(int max, int startIndex, int endIndex) {
this.max = max;
this.startIndex = startIndex;
this.endIndex = endIndex;
}
public int getMax() {
return max;
}
public void setMax(int max) {
this.max = max;
}
public int getStartIndex() {
return startIndex;
}
public void setStartIndex(int startIndex) {
this.startIndex = startIndex;
}
public int getEndIndex() {
return endIndex;
}
public void setEndIndex(int endIndex) {
this.endIndex = endIndex;
}
}
冒泡排序
[*] 排序逻辑
[*]相邻的元素两两比较，大的放右边，小的放左边
[*]第一轮循环结束，最大值已经找到，在数组的最右边
[*]第二轮循环只要在剩余的元素找最大值就可以了
[*]第二轮循环结束，次大值已经确定，第三轮循环继承在剩余数据中循环
[*] 核心
[*]相邻的元素两两比较，大的放右边，小的放左边
[*]第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，反面以此类推
[*]如果数组中有n个数据，总共我们只要实行n-1轮的代码即可
[*] 代码
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr > arr) {
// 左边数据比右边大，交换位置
int temp = arr;
arr = arr;
arr = temp;
}
}
}
}
选择排序
[*] 从0索引开始，拿着每一个索引上的元素跟反面的元素依次比较，小的放前面，大的放反面，以此类推
[*] 代码
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr > arr) {
// 左边数据比右边大，交换位置
int temp = arr;
arr = arr;
arr = temp;
}
}
}
}
插入排序
[*] 将0索引的元素到N索引的元素看作是有序的，把N+1索引的元素到末了一个当成是无序的
[*] 遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如碰到雷同数据，插在反面
[*] N的范围：0~最大索引
package com.gen.test;
public class InsertSortDemo {
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 1.找到无序索引起始位置
int startIndex = -1;
for (int i = 0; i < arr.length - 1; i++) {
if (arr > arr) {
startIndex = i + 1;
break;
}
}
// 2.遍历无序元素，依次插入到有序元素中
for (int i = startIndex; i < arr.length; i++) {
// 记录当前要插入数据的索引
int j = i;
while (j > 0 && arr < arr) {
// 交换位置
int temp = arr;
arr = arr;
arr = temp;
j--;
}
}
}
}
快速排序
第一轮：把0索引的数字作为基准数，确定基准数在数组中精确的位置。比基准数小的全部在左边，比基准数大的全部在右边
/**
* 快速排序
*
* @param arr 要排序的数组
* @param i 开始索引
* @param j 结束索引
*/
public static void quickSort(int[] arr, int i, int j) {
// 递归出口
if (i >= j) {
return;
}
int start = i;
int end = j;
// 记录基准数
int baseNum = arr;
while (start != end) {
// 从后往前找，找到比基准数小的元素
while (true) {
if (start >= end || arr < baseNum) {
break;
}
end--;
}
// 从前往后找，找到比基准数大的元素
while (true) {
if (start >= end || arr > baseNum) {
break;
}
start++;
}
// 把start和end元素进行交换
int temp = arr;
arr = arr;
arr = temp;
}
// 基准数归位
arr = arr;
arr = baseNum;
// 递归排序左边的数
quickSort(arr, i, start - 1);
// 递归排序右边的数
quickSort(arr, start + 1, j);
}
排序总结
[*]冒泡排序
[*]相邻的元素两两比较，小的放前面，大的放反面
[*]选择排序
[*]从0索引开始，拿着每一个索引上的元素跟反面的元素依次比较，小的放前面，大的放反面，以此类推
[*]插入排序
[*]将数组分为有序和无序两组，遍历无序数据，将元素插入有序序列中即可
[*]快速排序
[*]将排序范围中的第一个数字作为基准数，再定义两个变量start、end
[*]start从前去后找比基准数大的，end从后往前找比基准数小的
[*]找到之后交换start和end指向的元素，并循环这一过程，直到start和end处于同一个位置，该位置是基准数在数组中应存入的位置，再让基准数归位
[*]归位后的效果：基准数左边的，比基准数小，基准数右边的，比基准数大
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]