Java菜鸟篇

Java Basic-03
=====================================
1.什么是数组
???? 数组用来存储具有相同类型的一组数据，
???? 数组中的每一个数据称为元素，
???? 每一个元素通过下标来标识其位置（下标是0开始的）。
???? 数组中元素的类型必须相同。
??? 使用数组一般有如下四个步骤：
?????? 声明 -> 初始化? -> 赋值 -> 使用数组中的元素
=====================================
2 数组的声明
? Example：int[] arr1;//arr1是变量的名称，数组中元素的类型是int
?????????? double[] arr2; //arr2通常称为数组类型的变量
?????????? char[] arr3;
?????????? boolean[] arr4;
?????????? int arr5[];//合法的数组声明，但不常用
=====================================
3 数组的初始化
?3.1 静态初始化
?? Example： int[] arr1={1,2,3,5,8,13};
??????????? int[] arr2=new int[]{1,2,3};
???? (通过静态初始化，指明数组的长度为6，
???????????? 每一个元素的值分别是1，2，3，5，8，13)
?????? 静态初始化只能在声明数组时使用。
?---------------------------------------------
?3.2 动态初始化
?? Example：int[] arr1=new int[5];
???? (在内存中分配20个字节的空间，用来存放5个整数，
?????????????? 即数组的长度是5.同时变量arr1指向这个内存空间的初始地址)
????? 数组动态初始化之后每一个元素的初始值可以是:
????? 0、0.0、'\u0000'、false、null
?? -----------------------------------
?? 使用java.util.Arrays的方法toString(数组)来显示数组的内容
==============================================
4.数组的赋值
? 4.1 数组具有属性length,用来返回数组中元素的个数
??? Example：int[] arr={};
???????????? int len=arr.length;
? 4.2 访问数组中元素的语法： 数组变量名[下标]
????? 下标从0开始，范围是[0,length-1]。
????? 如果使用超出范围的下标，
????? 会出现ArrayIndexOutOfBoundsException异常?
==============================================
5.使用数组中的元素
? 5.1 循环输出数组中的元素
??? 1)使用for循环
????? Example：int[] arr={1,2,3};
????????????? for(int i=0;i<=arr.length-1;i++){
????????????? ...
????????????? }
??? 2)使用另一种形式的for循环(forEach循环)
????? Example:int[] arr={1,2,3};
????????????? for(int x:arr){
???????????????? //int是数组中元素的类型
???????????????? //x代表循环中数组的当前元素
????????????? }
==============================================
6.数组的复制与扩容
? *数组一旦定义，其元素的个数就是固定的。
? Example: int[] arr=new int[10];
? 5.1 数组的复制
??? 1)使用Arrays.copyOf(源数组,长度)来复制数组，
???? 用来将源数组中从0开始指定长度的元素复制到目标数组中。
???? Example: int[] arr2=Arrays.copyOf(arr,2);
???
??? 2)使用Arrays.copyOfRange(源数组，源起始位置，源结束位置)来赋值数组。
??? (包括起始位置的元素，但不包括结束位置的元素)
??? Example:int[] arr3=Arrays.copyOfRange(arr,1,3);//拷贝第1个和第2个元素

??? 3）使用System.arraycopy方法来复制数组
?????? arraycopy方法具有5个参数：
????????? (1)源数组
????????? (2)源数组中的起始位置
????????? (3)目标数组
????????? (4)目标数组中的起始位置
????????? (5)要复制的元素的个数
?????? Example:
?????????? int[] arr1={1,2,3,4,5,6};
?????????? int[] arr2=new int[10];
?????????? System.arraycopy(arr1,1,arr2,0,4);
??? 4)区分数组的复制和数组变量的赋值
?????? int[] arr1={1,2,3};
?????? int[] arr2=arr1;
?????? //将变量arr1赋值给arr2，arr1和arr2此时是同一个数组
? ---------------------------------------------
? 5.1 数组的扩容
???? 使用Arrays的copyOf方法可以完成对一个数组的扩容。
???? Example: int[] arr=new int[10];
????????????? arr=Arrays.copyOf(arr,arr.length+1);
===========================================
6.什么是算法：
?? 算法是解决特定问题的步骤，
?? 常用的算法有：数组排序、数组的二分查找法、递归算法等。
===========================================
7.数组排序的算法一：选择排序
? 7.1 思路：假定数组的长度为n,
??????????????????????? 从0到n-2进行循环，对于循环中的每一个元素x，
??????????????????????? 在数组后面的元素中选择一个最小的元素和x互换。
? 7.2 伪代码：
???????? for i=0 to n-2? //外层循环从[0,n-2]
??????????? for j=i+1 to n-1 //内层循环从[i+1,n-1]
???????????????????????????????? 在[i+1,n-1]范围内找到最小元素的位置least
??????????????????????????? 交换位置i和位置least的元素

/**
?* 使用选择排序：
?*/
public static void select(int[] score) {
? for (int i = 0; i < score.length - 1; i++) {
???? ?int least = i;
???? ?// [i+1,n-1]
???? ?for (int j = i + 1; j < score.length; j++) {
???????? ?if (score[j] < score[least])
????????????? least = j;
????????? }
???????? ?// 交换i与least两个位置的元素
???????? if (i != least) {
??????????? int temp = score[i];
?????????? ?score[i] = score[least];
??????????? score[least] = temp;
?????? }
? ?}

}
===========================================
8.数组排序的算法二：冒泡排序
? 8.1 伪代码：
???????? for i=0 to n-2? //外层循环[0,n-2]
??????????? for j=n-1 downto i+1
???????????????????????????????? 依次比较j和j-1两个位置的元素，
???????????????????????????????? 如果位置j的元素小于位置j-1的元素，
???????????????????????????????? 则交换两个位置的元素。

/**
? * 采用冒泡排序的算法对数组arr进行排序
? * @param arr
??*/
? public static void sort(int[] arr){
??? ?//外层循环[0,n-2]
??? ?for(int i=0;i<arr.length-1;i++){
???? ?//内层循环[n-1,i+1]
??? ???? for(int j=arr.length-1;j>i;j--){
??? ??????? //在内层循环中依次交换次序不正确的元素
??? ?????? ?if(arr[j]<arr[j-1]){
??? ?????????? int temp=arr[j];
??? ????????? ?arr[j]=arr[j-1];
??? ???? ??? ??arr[j-1]=temp;
??? ?? ?? ?}
??? ?? ?}
??? ?}
? }

============================================
9.数组排序的算法三：插入排序
? 9.1 思路：假定数组arr的长度为n，
??????????????????????? 将arr分成前组[0,i]和后组[i,n-1],其中i从1..n-1.
?????????????????????? 并将位置i的元素插入到前组对应的位置上。
? 9.2 伪代码：
??????? int[] arr;
??????? for i=1 to n-1
?????????? int x=arr[i];//x是需要寻找插入位置的元素
?????????? for j=i downto 1 && x<arr[j-1]????????????
????????????? arr[j]=arr[j-1];//将j-1位置的元素后移1位
?????????? //内层循环结束后，j就是x的插入位置
?????????? arr[j]=x;
????? (插入排序效率最高，冒泡排序效率最低，选择排序效率居中.)

/**
?* 插入排序代码：
?*/
public static void sort(int[] arr) {
?? ?// i从[1,n-1]
??? for (int i = 1; i < arr.length; i++) {
????? ?// 记录i位置的元素x
??? ???int x = arr[i];
?? ? ??// j从[i,1],在前组[0,i]中寻找x的合适位置
?? ????int j;
?? ? ??for (j = i; j > 0 && x < arr[j-1]; j--) {
??? ?? ???// 将j-1位置的元素后移1位
????? ????arr[j] = arr[j - 1];
???? ??}
??? ???// 在内层循环结束后，j就是x的插入位置
??? ? ?arr[j] = x;
? ? }
}

=============================================
10.使用Arrays类的sort方法来排序
?? Example: Arrays.sort(数组);
=============================================
11.递归算法
?11.1什么是递归算法？
??在一个方法内部调用当前方法，成为递归算法。
?11.2递归算法的必要条件
??在递归算法内，必须包含一个出口以结束递归调用。
?Task：通过递归算法产生如下的序列： 1 1 2 3 5 8 13 21 34 55 89...
?斐波纳契序列公式：f(n)=f(n-1)+f(n+2),f(2)=f(1)
?11.3递归的优点是算法简洁，缺点是内存占用大，执行效率低一些
??递归算法比较适合于对树形结构的操作。
???????
// 将arr中元素混排
??Random random = new Random();
??for (int i = 0; i < 10000; i++) {
???// 产生[i,10000)之间的随机数
???int r = random.nextInt(10000 - i) + i;
???// 交换i和r位置的元素
???int temp = arr[i];
???arr[i] = arr[r];
???arr[r] = temp;
??}?