2018-04-27
与其临渊羡鱼，不如退而结网
数组高级——多维数组
一、定义
二、初始化和内存分析
以二维数组为例
- 静态初始化：
int[][] arr = new int[][]{
{1,2,3},
{4,5},
{6}
};
- 动态初始化：
int[][] arr = new int[3][5]; //创建一个长度为3的二维数组，每一个元素（一维数组）的长度为5
三、java5对数组的新语法支持
-
增强for循环：foreach
foreach的语句格式：
for(数组元素类型t 数组元素变量x : 遍历对象obj){
引用了x的java语句;
}
需求：定义一个数组使用循环迭代出数组的每一个元素
代码：
1 //增强for循环：foreach 2 3 class ForEachDemo 4 { 5 public static void main(String[] args) 6 { 7 //使用for循环迭代元素 8 int[] arr = new int[]{10,20,30,40,50}; 9 for(int index = 0 ; index < arr.length; index++){ 10 System.out.println(arr[index]); 11 } 12 System.out.println("------------------"); 13 //使用foreach循环迭代元素 14 for(int ele : arr){ 15 System.out.println(ele); 16 } 17 } 18 }
输出结果：
- 方法的可变参数 （变的是参数的个数，不是参数类型）
需求：定义一个方法来统计使用数组传递的总和
普通方法：
1 //方法的可变参数 2 3 class VarArgsDemo 4 { 5 public static void main(String[] args) 6 { 7 double[] ps = new double[]{1.0,2.0,3.0,4.0,5.0}; 8 double sum = getSum(ps); 9 System.out.println(sum); 10 } 11 //计算商品的总和(普通方法) 12 static double getSum(double[] arr){ 13 double sum = 0.0; 14 for(double price : arr){ 15 sum = sum + price; 16 } 17 return sum; 18 } 19 }
输出结果：15.0
可变参数方法：
1 //方法的可变参数 2 3 class VarArgsDemo 4 { 5 public static void main(String[] args) 6 { 7 double[] ps = new double[]{1.0,2.0,3.0,4.0,5.0}; 8 double sum = getSum(ps);
9 System.out.println(sum);
10 }
11 //计算商品的总和(可变参数方法)
12 static double getSum(double ... arr){
13 double sum = 0.0;
14 for(double price : arr){
15 sum = sum + price;
16 }
17 return sum;
18 }
19 }
输出结果：15.0
可变参数必须作为方法的最后一个参数，避免参数的歧义
推论：方法最多只有一个可变参数
四、数组算法
- 数组元素拷贝
参考博客 java System.arrayCopy使用说明
学会使用API
2.排序算法
排序：安照指定顺序排列出来
升序：从小到大
降序：从大到小
排序的分类： 选择排序（直接选择排序、堆排序）， 交换排序（冒泡排序、快速排序）， 插入排序（直接插入排序、二分法插入排序、shell排序）， 归并排序等。
- 冒泡排序
a)原理：比较两个相邻的元素，将值大的元素交换至右端。
b)思路：依次比较相邻的两个数，若大于则交换位置。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。
c)举例说明：要排序数组：int[] arr={6,3,8,2,9,1};
第一趟排序：
第一次排序：6和3比较，6大于3，交换位置： 3 6 8 2 9 1
第二次排序：6和8比较，6小于8，不交换位置：3 6 8 2 9 1
第三次排序：8和2比较，8大于2，交换位置： 3 6 2 8 9 1
第四次排序：8和9比较，8小于9，不交换位置：3 6 2 8 9 1
第五次排序：9和1比较：9大于1，交换位置： 3 6 2 8 1 9
第一趟总共进行了5次比较， 排序结果： 3 6 2 8 1 9
---------------------------------------------------------------------
第二趟排序：
第一次排序：3和6比较，3小于6，不交换位置：3 6 2 8 1 9
第二次排序：6和2比较，6大于2，交换位置： 3 2 6 8 1 9
第三次排序：6和8比较，6大于8，不交换位置：3 2 6 8 1 9
第四次排序：8和1比较，8大于1，交换位置： 3 2 6 1 8 9
第二趟总共进行了4次比较， 排序结果： 3 2 6 1 8 9
---------------------------------------------------------------------
第三趟排序：
第一次排序：3和2比较，3大于2，交换位置： 2 3 6 1 8 9
第二次排序：3和6比较，3小于6，不交换位置：2 3 6 1 8 9
第三次排序：6和1比较，6大于1，交换位置： 2 3 1 6 8 9
第二趟总共进行了3次比较， 排序结果： 2 3 1 6 8 9
---------------------------------------------------------------------
第四趟排序：
第一次排序：2和3比较，2小于3，不交换位置：2 3 1 6 8 9
第二次排序：3和1比较，3大于1，交换位置： 2 1 3 6 8 9
第二趟总共进行了2次比较， 排序结果： 2 1 3 6 8 9
---------------------------------------------------------------------
第五趟排序：
第一次排序：2和1比较，2大于1，交换位置： 1 2 3 6 8 9
第二趟总共进行了1次比较， 排序结果： 1 2 3 6 8 9
---------------------------------------------------------------------
最终结果：1 2 3 6 8 9
---------------------------------------------------------------------
由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
代码实现：
/* * 冒泡排序 */ public class BubbleSort { public static void main(String[] args) { int[] arr={6,3,8,2,9,1}; System.out.println("排序前数组为："); for(int num:arr){//for-each循环 System.out.print(num+" "); } for(int time = 0; i < arr.length-1; i++){//外层循环控制排序趟数 for(int j = 0;j < arr.length-1-time; j++){//内层循环控制每一趟排序多少次 if(arr[j]>arr[j+1]){ int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } System.out.println(); System.out.println("排序后的数组为："); for(int num:arr){ System.out.print(num+" "); } } }
-
- 选择排序
a) 原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）
b)直接选择排序算法的思想比较简单：（假设数据放在一个数组a中，且数组的长度是N）
1：从a[0]-a[N-1]中选出最小的数据，然后与a[0]交换位置
2：从a[1]-a[N-1]中选出最小的数据，然后与a[1]交换位置（第1步结束后a[0]就是N个数的最小值）
3：从a[2]-a[N-1]中选出最小的数据，然后与a[2]交换位置（第2步结束后a[1]就是N-1个数的最小值）
以此类推，N-1次排序后，待排数据就已经按照从小到大的顺序排列了。
c)举例：
//选择排序 public class SelectionSort { public static void main(String[] args) { int[] arr={1,3,2,45,65,33,12}; System.out.println("交换之前："); for(int num:arr){ System.out.print(num+" "); } //选择排序的优化 for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序 int k = i; for(int j = k + 1; j < arr.length; j++){// 选最小的记录 if(arr[j] < arr[k]){ k = j; //记下目前找到的最小值所在的位置 } } //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换 if(i != k){ //交换a[i]和a[k] int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; } } System.out.println(); System.out.println("交换后："); for(int num:arr){ System.out.print(num+" "); } } }
3.搜索算法
从指定数组中去搜索某一个元素的索引是多少
- 线性搜索（从头搜到尾或从尾搜到头）
- 二分搜索（二分查找）
a)二分查找又称折半查找，它是一种效率较高的查找方法。
折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小 于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
b)折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
c)二分算法步骤描述
① 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2
② 用待查关键字值与中间位置的关键字值进行比较；
若相等，则查找成功
若大于，则在后（右）半个区域继续进行折半查找
若小于，则在前（左）半个区域继续进行折半查找
③ 对确定的缩小区域再按折半公式，重复上述步骤。
最后，得到结果：要么查找成功， 要么查找失败。折半查找
4.Java自带数组工具类Arrays类
查找API java.util.Arrays