数组的高级操作
1. 查找
1.1 普通查找
需求：定义方法实现，查找某元素在数组中第一次出现的位置（索引），如果没有，返回-1。
分析：
参数列表：需要查找的数组 和 元素
返回值类型：找到的位置 int
遍历数组，依次查找即可
代码：
public static int search(int[] arr, int value) {
if (arr == null) {
throw new RuntimeException("数组为空");
}
// 定义变量表示查找的索引
int index = -1;
// 遍历查询
for (int i = 0; i < arr.length; i++) {
if (value == arr[i]) {
index = i;
// 如果找到，结束循环，不再查找后续元素
break;
}
}
return index;
}1.2 二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找前提：
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
查找过程：
1、首先，假设表中元素是按升序排列，将表中间位置记录关键字与查找关键字比较，如果两者相等，则查找成功；
2、否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
3、重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
代码示例：
public static int binarySearch(int[] arr, int value) {
// 查找的范围
int start = 0;
int end = arr.length - 1;
// 循环查找
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] < value) {
// 如果值大，查询的起始索引改变
start = mid + 1;
} else if (value < arr[mid]) {
// 如果值小，查询的结束索引改变
end = mid - 1;
} else {
// 找到了 返回索引
return mid;
}
}
// 循环结束没有return，没找到，返回 负的插入点-1
return -(start + 1);
}2. 排序
2.1 冒泡排序
冒泡排序（Bubble Sort），是一种比较简单的排序算法。原理如下：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
对数组{5, 1, 4, 2, 8}进行冒泡排序的过程如下图所示：
第一轮排序：
第二轮排序：
第三轮排序：
第四轮排序：
代码：
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[j] > arr[j + 1]) {
// 交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}2.2 选择排序
选择排序（Selection sort）的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
排序过程如下图所示：
代码：
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 记录最小值出现的位置
int mark = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[mark]) {
mark = j;
}
}
if (mark != i) {
// 交换
int temp = arr[mark];
arr[mark] = arr[i];
arr[i] = temp;
}
}
}
