9. 数组的常见算法
2022年6月6日
9. 数组的常见算法
数组中涉及的常见算法
- 数组元素的赋值
- 求数值型数组中元素的最大值、最小值、平均数、总和等
- 数组的复制、反转、查找(线性查找、二分法查找)
- 数组元素的排序算法
数组元素的赋值
使用二维数组打印一个 10 行杨辉三角。
提示:
- 第一行有 1 个元素, 第 n 行有 n 个元素
- 每一行的第一个元素和最后一个元素都是 1
- 从第三行开始, 对于非第一个元素和最后一个元素的元素。
public static void main(String[] args) {
int[][] arr = new int[10][10];
for (int[] irr : arr) {
Arrays.fill(irr, 1);
}
for (int i = 2; i < arr.length; i++) {
for (int j = 1; j < i; j++) {
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
}
}
for (int i = 0; i < arr.length; i++) {
for (int j = arr.length; j > i; j--) {
System.out.print(" ");
}
for (int j = 0; j <= i; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
数组计算、复制、反转
定义一个 int 型的一维数组，包含 10 个元素，分别赋一些随机整数，然后求出所有元素的最大值，最小值，和值，平均值，并输出出来。要求：所有随机数都是两位数。
提示：随机两位数 (int)(Math.random() * 90 + 10)。
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 90 + 10);
System.out.print(arr[i] + " ");
}
System.out.println();
int max = 0;
int min = 0;
int avg = 0;
int sum = 0;
for (int i : arr) {
sum += i;
for (int i1 : arr) {
if (i > i1) {
max = i;
break;
}
if (i < i1) {
min = i;
break;
}
}
}
avg = (max + min) / 2;
System.out.println(max + " " + min + " " + avg + " " + sum);
}
声明一个 int[] 类型的数组，int [] arrayA= {2,3,5,7,11,13,17,19}，声明另外一个 int 数组 arrayB 并复制 arrayA 里的内容。修改 arrayB 中的偶索引元素，使其等于索引值(如 arrayB[0]=0,arrayB[2]=2)。打印出 arrayA 和 arrayB。
public static void main(String[] args) {
int[] arrayA = {2, 3, 5, 7, 11, 13, 17, 19};
int[] arrayB = new int[arrayA.length];
for (int i : arrayA) {
System.out.print(i + " ");
}
System.out.println();
for (int i = 0; i < arrayA.length; i++) {
arrayB[i] = arrayA[i];
}
for (int i : arrayB) {
System.out.print(i + " ");
}
System.out.println();
for (int i = 0; i < arrayB.length; i++) {
arrayB[i] = i;
}
for (int i : arrayB) {
System.out.print(i + " ");
}
}
定义如下数组 String [] arr = {“A”,“B”,“C”,“D”,“E”,“F”},并反转该数组的内容。
public static void main(String[] args) {
String[] arr = {"A", "B", "C", "D", "E", "F"};
String tmp = "";
for (int i = 0; i < arr.length / 2; i++) {
tmp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = tmp;
}
for (String s : arr) {
System.out.print(s + " ");
}
}
数组的查找
线性查找
定义如下数组 int [] numbers = {1,2,5,3,6,3,9,3,15}，查找数组中元素是 3 的倍数的元素个数。
public static void main(String[] args) {
int[] numbers = {1, 2, 5, 3, 6, 3, 9, 3, 15};
int tmp = 0;
for (int number : numbers) {
if (number % 3 == 0) {
tmp++;
}
}
System.out.println(tmp);
}
二分查找
/*
二分法查找
1.二分法查找是建立在已经排序的基础之上的。
2.以下程序分析从小到大排序。
3.这个数组中没有重复的元素.
1 3 5 9 11 13 56
以上是一个已经排好序的int类型的数组,要求快速找出13这个元素的下标。
1 3 5 9 11 13 56
int begin = 0;
int end = 6;
int mid = 3;
中间元素是9, 9<13
begin = mid + 1; 4
end = 6;
mid = 5;
中间元素是13. 13==13
*/
public class MyArrays {
public static void main(String[] args) {
int[] a = {1, 3, 4, 5, 7, 8, 9, 10, 23, 25, 29};
int destElement = 100;
// 要求从a数组中查找10这个元素的下标
int index = binarySearch(a, destElement); // 如果找到则返回元素的下标，如果找不到统一返回 -1
System.out.println((index == -1) ? destElement + "元素不存在！" : destElement + "在数组中的下标是：" + index);
}
// 折半查找的核心算法
public static int binarySearch(int[] a, int destElement) {
int begin = 0;
int end = a.length - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (a[mid] == destElement) {
return mid;
} else if (a[mid] > destElement) {
end = mid - 1;
} else if (a[mid] < destElement) {
begin = mid + 1;
}
}
return -1;
}
}
数组的排序
排序：是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
分类：稳定排序、不稳定排序。
稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。
稳定排序:冒泡，插入，基数，归并
不稳定排序:选择，快速，希尔
衡量排序算法的优劣：
- 时间复杂度：分析关键字的比较次数和记录的移动次数
- 空间复杂度：分析排序算法中需要多少辅助内存
- 稳定性：若两个记录 A 和 B 的关键字值相等，但排序后 A、B 的先后次序保持不变，则称这种排序算法是稳定的。
冒泡排序
冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
- 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。
/*
冒泡排序算法：
int类型的数组：3 1 6 2 5
*/
public class BubbleSort {
public static void main(String[] args) {
int[] a = {3, 1, 6, 2, 5};
// 开始排序
for (int i = a.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
// 交换位置
int temp;
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
// 遍历
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，
- 然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。
/*
选择排序：
3 1 6 2 5
算法：找出最小值，然后这个最小值和最前面的数据交换位置。
*/
public class SelectSort {
public static void main(String[] args) {
int[] a = {3, 1, 6, 2, 5};
// 选择排序
for (int i = 0; i < a.length - 1; i++) {
// 假设第一个数据是最小值
// 记录最小值元素的下标
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) {
// 给min重新赋值
min = j;
}
}
// 考虑交换位置.
if (min != i) {
int temp;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
// 输出
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
排序算法性能对比
Arrays 工具类
java.util.Arrays 类即为操作数组的工具类，包含了用来操作数组（比如排序和搜索）的各种方法。
boolean equals(int[] a,int[] b)：判断两个数组是否相等。String toString(int[] a)：输出数组信息。void fill(int[] a,int val)：将指定值填充到数组之中。void sort(int[] a)：对数组进行排序(快速排序)。int binarySearch(int[] a,int key)：对排序后的数组进行二分法检索指定的值。