数组
声明
type[] var; 或 type var[];
Java语言中声明数组时不能指定其长度(数组中元素的数)， 例如： int a[5]; //非法
初始化
动态初始化
数组声明且为数组元素分配空间 与 赋值的操作分开进行。
int[] arr = new int[3];//声明+初始化
arr[0] = 3;
arr[1] = 9;
arr[2] = 8;
String names[];//声明
names = new String[3];//初始化
names[0] = “钱学森”;
names[1] = “邓稼先”;
names[2] = “袁隆平”;
静态初始化
在定义数组的同时就为数组元素分配空间并赋值。
//声明+初始化
int[] arr0 = new int[]{3,9,8};
int[] arr1 = {3,9,8};//类型推断
String[] names = {“李四光”,“茅以升”,“华罗庚”}//类型推断
//先声明，再初始化
int[] arr2;
arr2 = new int[]{3,9,8};//此处“new int[]”不能省略，因为无法类型推断
元素的引用
定义并用运算符new为之分配空间后，才可以引用数组中的每个元素。
数组元素的引用方式：数组名[数组元素下标]
说明：长度为n的数组合法下标取值范围：0 —>n-1
数组的属性length
每个数组都有一个属性length指明它的长度，例如：a.length 指明数组a的长度(元素个数)
说明：数组一旦初始化，其长度是不可变的
数组元素的默认初始化值
数组是引用类型，它的元素相当于类的成员变量，因此数组一经分配空间，其中的每个元素也被按照成员变量同样的方式被隐式初始化。
对于基本数据类型而言，默认初始化值各有不同
对于引用数据类型而言，默认初始化值为null(注意与0不同！)
| 数组元素类型 | 元素默认初始值 |
|---|---|
| byte | 0 |
| short | 0 |
| int | 0 |
| long | 0L |
| float | 0.0F |
| double | 0.0 |
| char | 0 或写为:’\u0000’(表现为空) |
| boolean | false |
| 引用类型 | null |
一维数组的内存解析
内存的简化结构
练习一
升景坊单间短期出租4个月，550元/月（水电煤公摊，网费35元/月），空调、卫生间、厨房齐全。 屋内均是IT行业人士，喜欢安静。所以要求来租者最好是同行或者刚毕业的年轻人，爱干净、安静。
public class ArrayTest {
public static void main(String[] args) {
int[] arr = new int[]{8,2,1,0,3};
int[] index = new int[]{2,0,3,2,4,0,1,3,2,3,3};
String tel = "";
for(int i = 0;i < index.length;i++){
tel += arr[index[i]];
}
System.out.println("联系方式：" + tel);
}
}
二维数组的声明与初始化
//二维数组的声明与初始化
int[] arr = new int[]{1,2,3};//一维数组
//静态初始化
int[][] arr1 = new int[][]{{1,2,3},{4,5},{6,7,8}};
//动态初始化1
String[][] arr2 = new String[3][2];
//动态初始化2
String[][] arr3 = new String[3][];
arr3[1] = new String[4];
二维数组的遍历
for(int i=0;i<arr1.length;i++){
for(int j=0;j>arr1[i].length;j++){
System.out.print(arr4[i][j]+'\t');
}
System.out.println();
}
/*输出：
1 2 3
4 5
6 7 8*/
（因为数组用堆储存的性质，二维数组并不是连续储存的，每行的元素个数可以不同，因此需要.length属性）
二维数组的默认初始化值
若直接输出arr1或arr1[0]，得到形如：[[I@XXXXXXXX或[I@XXXXXXXX的地址。其中几个[代表它是几维数组，I代表int，XXXXXXXX代表十六进制地址
算法
赋值和复制
赋值操作：array2=array1;//同一个地址
复制操作：int[] arr2=new int[arr1.length]; 再for(;;)...
二分法查找
//二分法查找：要求此数组必须是有序的。
int[] arr3 = new int[]{-99,-54,-2,0,2,33,43,256,999};
boolean isFlag = true;
int number = 256;
int head = 0;//首索引位置
int end = arr3.length - 1;//尾索引位置
while(head <= end){
int middle = (head + end) / 2;
if(arr3[middle] == number){
System.out.println("找到指定的元素，索引为：" + middle);
isFlag = false;
break;
}else if(arr3[middle] > number){
end = middle - 1;
}else{//arr3[middle] < number
head = middle + 1;
}
}
if(isFlag){
System.out.println("未找打指定的元素");
}
排序
十大内部排序算法
选择排序：直接选择排序、堆排序
交换排序：冒泡排序、快速排序
插入排序：直接插入排序、折半插入排序、希尔排序（Shell排序）
归并排序
桶排序
基数排序
算法的5大特征
输入，输出，有穷性，确定性，可行性
冒泡排序
基本思想：通过对待排序序列从前向后、一次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部逐渐移向后部。
因为排序过程中，个元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换，从而减少不必要的比较。
结束条件：在任何一趟进行过程中，未出现交换。
public class BubbleSort {
public static void bubbleSort(int[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
for (int i = 0; i < arrayLength - 1; i++) {
boolean flag = false;
for (int j = 0; j < arrayLength - 1 - i; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
flag = true;
}
}
System.out.println(java.util.Arrays.toString(data));
if (!flag)
break;
}
}
public static void main(String[] args) {
int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
从冒泡排的算法可以看出，若待排的元素为正序，则只需进行一趟排序，比较次数为(n-1)次，移动次数为0；若待排序的元素为逆序，则需进行n-1趟排序，比较次数为(n^2-n)/2，移动次数为3(n^2-n)/2，因此时间复杂度为O(n^2)。由于其中的元素移动比较多，所以属于内部排序中速度较慢的一种。
因为冒泡排序只进行元素间的顺序移动，所以是一个稳定的算法。
快速排序
基本思想：任取待排序列中的某个元素作为标准（也称支点、界点，一般取第一个元素），通过一次划分，将待排元素分为左右两个子序列，左子序列元素的排序码均小于基准元素的排序码，右子序列的排序码则大于或等于基准元素的排序码，然后分别对两个子序列继续进行划分，直至每一个序列只有一个元素为止。最后得到的序列就是有序序列。
一次划分的具体过程：
- low指向待划分区域首元素，high指向待划分区域尾元素；
- R[0]=R[low]（为了减少数据的移动将作为标准的元素暂存到R[0]中，最后再放入最终位置）；
- high从后往前移动直到R[high].key<R[0].key;
- R[low]=R[high], low++;
- low从前往后移动直到R[low].key>=R[0].key;
- R[high]=R[low], high--;
- goto 3;
- 直到low==high时，R[low]=R[0]（即将作为标准的元素放到其最终位置）
概括地说，以此划分就是从表的两段交替地向中间进行扫描，将晓得放到左边，大的放到右边，作为标准的元素放到中间。
快速排序的时间复杂度为O(nlog2 n)
void quickSort(datatype R[],int s,int t){
if(s<t){
i=partition(R,s,t);//将表一分为二
quickSort(R,s,i-1);//对左子表序列进行快速排序
quickSort(R,i+1,t);//对右子表序列进行快速排序
}
}
int partition(datatype R[],int low,int high){
R[0]=R[low];//暂存临界点到R[0]中
while(low<high){//从表的两段交替地向中间扫描
while(low<high&&R[high].key>=R[0].key) high--;//在右端扫描
if(low<high){
R[low]=R[high];//把比界点小的元素放到界点前面
low++;
}
while(low<high&&R[low].key<R[0].key) low++;//在左端扫描
if(low<high){
R[high]=R[low];//把比界点大的元素放到界点后面
high--;
}
}
R[low]=R[0];//将界点元素放到其中间位置
return low;//返回界点元素所在的位置
}
public class QuickSort {
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(int[] data, int start, int end) {
if (start < end) {
int base = data[start];
int low = start;
int high = end + 1;
while (true) {
while (low < end && data[++low] - base <= 0);
while (high > start && data[--high] - base >= 0);
if (low < high) {
swap(data, low, high);
} else {
break;
}
}
swap(data, start, high);
subSort(data, start, high - 1);//递归调用
subSort(data, high + 1, end);
}
}
public static void quickSort(int[] data){
subSort(data,0,data.length-1);
}
public static void main(String[] args) {
int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
从快速排序算法的递归树可知，快读排序的趟数取决于递归树的高度。
快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。最大递归调用层次数与递归树的高度一致。理想情况为[log2 (n+1)]上取整；最坏情况即待排序对象序列已经按其排序码从小到大排好序的情况下，其递归树成为单支树，深度为n。因此，快速排序最好的空间复杂度为O(log2 n)，最坏的空间复杂度为O(n)，即快速排序所需用的辅助空间。
快速排序是一种不稳定的排序方法。
排序算法性能对比
Math.random
random() Returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0.
Math.random()：[0.0,1)
公式：获取[a,b]范围的随机数：(int)(Math.random()*(b-a+1))+a
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) | 对排序后的数组进行二分法检索指定的值。 |
//1.boolean equals(int[] a,int[] b)
boolean isEquals=Arrays.equals(arr1,arr2);
//2.String toString(int[] a)
System.out.println(Arrays.toString(arr);
//3.void fill(int[] a,int val)
Arrays.fill(arr,10);//将arr[]中的所有元素赋值为10
//4.void sort(int[] a)
Arrays.sort(arr);//对数组进行快速排序
//5.int binarySearch(int[] a,int key)
int[] arr1=new int[](-98,-34,2,34,54,66,79,105,210,333)
int index=Arrays.binarySearch(arr1,211);
if(index>=0){
System.out.println(index);//找到会返回索引位置
}else{
System.out.println("未找到")；//未找到会返回一个负数
}
.equals
e1.equals(e2)
返回值boolean
| equals |
|---|
| public static boolean equals(Object[] a,Object[] a2) |
Returns true if the two specified arrays of Objects are equal to one another. The two arrays are considered equal if both arrays contain the same number of elements, and all corresponding pairs of elements in the two arrays are equal. Two objects e1 and e2 are considered equal if (e1==null ? e2==null : e1.equals(e2)). In other words, the two arrays are equal if they contain the same elements in the same order. Also, two array references are considered equal if both are null. |
Parameters: a - one array to be tested for equality, a2 - the other array to be tested for equality |
Returns: true if the two arrays are equal |
java.util.Arrays.toString
| toString |
|---|
| public static String toString(int[] a) |
Returns a string representation of the contents of the specified array. The string representation consists of a list of the array's elements, enclosed in square brackets ("[]"). Adjacent elements are separated by the characters ", " (a comma followed by a space). Elements are converted to strings as by String.valueOf(int). Returns "null" if a is null. |
Parameters: a - the array whose string representation to return |
Returns: a string representation of a |
常见异常
ArrayIndexOutOfBoundsException：数组角标越界异常
合理范围：[0,arr.length-1]
越界：arr[-1]，arr[arr.length]
NullPointerException：空指针异常
int[] arr=null;
arr[0];
