- 对数组操作最基本的动作: 存和取
- 核心思想: 就是对角标的操作
数组常见操作:
1, 遍历
2, 获取最大值和最小值
3, 排序
4, 查找
5, 折半查找
// 1. 遍历
int[] arr = {23,435,46,576,456,4,4,56,574,756}
for(int x=0; x<arr.length; x++)
{
// 格式良好
System.out.println("arr["+x+"]="+arr[x]+";");
}
/* 2. 求最值(最大值, 最小值)
思路:
1. 需要进行比较, 并定义变量记录住每次比较后较大的值
2. 对数组中的元素进行遍历取出, 和变量中记录的元素进行比较
如果遍历到的元素大于变量中记录的元素, 就用变量记录住大的值
3. 遍历结束, 该变量记录就是最大值
定义一个功能来实现
明确一, 结果
是数组中的元素, int类型
明确二, 未知内容
数组
*/
第一种方式:
public static int getMax_1(int[] arr)
{
// 定义变量,记录较大的值
int max = arr[0];
// x=1 是因为 max = arr[0]; 下标为 0 的元素直接和下标为 1 的元素进行比较即可
for(int x=1; x<arr.length; x++)
{
if(arr[x]>max)
max = arr[x];
}
return max;
}
第二种方式:
public static int getMax_2(int[] arr)
{
// 定义变量, 记录较大元素的角标
int maxIndex = 0;
for(int x=1; x<arr.length; x++)
{
if(arr[x]>arr[maxIndex])
maxIndex = x;
}
return arr[maxIndex];
}
// 3.1 选择排序
// 大圈套小圈, for 嵌套(尖朝下三角形)
// 由于直接在数组本身进行操作,故没有返回值
public static void selectSort(int[] arr)
{
// 数组本身的遍历(外循环), 注意此时的条件
for(int x=0; x<arr.length-1; x++)
{
// 数组中一个元素,和它后面每一元素比较(内循环)
for(int y=x+1; y<arr.length; y++)
{
// 外循环和内循环的值进行比较
// 如果前者大于后者, 互换位置
if(arr[x]>arr[y])
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}
// 为提高性能,可以将最小值的角标记录,比较完成后,在完成换位
public static void selectSort_2(int[] arr)
{
for(int x=0; x<arr.length-1; x++)
{
int num = arr[x];
int index = x;
for(int y=x+1; y<arr.length; y++)
{
if(num>arr[y])
{
num = arr[y];
index = y;
}
}
if(index!=x)
{
int temp = arr[x];
arr[x] = arr[index];
arr[index] = arr[x];
}
}
}
// 3.2 冒泡排序
// 大圈套小圈
public static void bubbleSort(int[] arr)
{
// 外循环控制循环次数
for(int x=0; x<arr.length-1; x++)
{
// 内循环进行相邻比较
// 其中 -1 为了避免角标越界
// -x 为了让外循环增加一次,内循环参与比较的元素递减
for(int y=0; y<arr.length-1-x; y++)
{
if(arr[y]>arr[y+1])
{
int temp = arr[y];
arr[y] = arr[y+1];
arr[y+1] = temp;
}
}
}
}
// 4. 查找
// 查找数组中是否存在指定元素,存在,返回第一次出现的下标值
public static int getIndex(int[] arr, int key)
{
for(int x=0; x<arr.length; x++)
{
if(arr[x]==key)
return x;
}
// 如果数组中没有要查找的元素, 而本函数使有返回值的
// 因此,必须要有下面这句.否则,编译失败.
return -1;
}
// 5. 折半查找 (二分查找)
// 前提: 被查找的数组必须是**有序**的
// 需求: 查找 1~100 之间的一个数字
// 第一种方式:
public static void halfSearch(int[] arr, int key)
{
// 数组中元素并不一定按照特定顺序排列,
// 但是数组中元素的角标从小到大排列的
int max, min, mid;
min = 0;
max = arr.length-1;
mid = (max + min)/2;
while(arr[mid] != key)
{
if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
if(max<min)
return -1;
mid = (max+min)/2;
}
return mid;
}
// 第二种方式:
public static void halfSearch_2(int[] arr, int key)
{
int min, max, mid;
min = 0;
max = arr.length-1;
while(min <= max)
{
mid = (min+max)>>1; //左移1位,相当于除以2
if(key>arr[mid])
min = mid + 1;
else if(key<arr[mid])
max = mid - 1;
else
return mid;
}
return -1;
}
/*
思考:
给定一个有序的数组,如果往该数组中存储一个元素,并保证这个数组还是有序的,
那么这个元素存储的角标如何获取?
*/
// 备注: java 自带的二分查找: Arrays.binarySearch();
// 如果找不到该元素,返回: -min-1, 即 -元素插入点 - 1;
_参考资料:_
- [JavaSE 基础视频(毕向东)](https://www.bilibili.com/video/av3087889/#page=2)