1、数组进阶
1.1、常见的算法：
	排序算法：
		冒泡排序算法
		选择排序算法

	查找算法：
		二分法查找
	
	以上算法在以后的java实际开发中我们不需要使用的。
	因为java已经封装好了，直接调用就行。
	只不过以后面试的时候，可能会有机会碰上。

1.2、算法实际上在java中不需要精通，因为java中已经封装好了， 要排序就调用方法就行。例如：java中提供了一个数组工具类： java.util.Arrays Arrays是一个工具类。 其中有一个sort()方法，可以排序。静态方法，直接使用类名调用就行。
2、冒泡排序：
参与比较的数据：9 8 10 7 6 0 11
第1次循环：
8 9 10 7 6 0 11 (第1次比较：交换)
8 9 10 7 6 0 11 (第2次比较：不交换)
8 9 7 10 6 0 11 (第3次比较：交换)
8 9 7 6 10 0 11 (第4次比较：交换)
8 9 7 6 0 10 11 (第5次比较：交换)
8 9 7 6 0 10 11 (第6次比较：不交换)
最终冒出的最大数据在右边：11

参与比较的数据：8 9 7 6 0 10
第2次循环：
8 9 7 6 0 10（第1次比较：不交换）
8 7 9 6 0 10（第2次比较：交换）
8 7 6 9 0 10（第3次比较：交换）
8 7 6 0 9 10（第4次比较：交换）
8 7 6 0 9 10（第5次比较：不交换）

参与比较的数据：8 7 6 0 9
第3次循环：
7 8 6 0 9（第1次比较：交换）
7 6 8 0 9（第2次比较：交换）
7 6 0 8 9（第3次比较：交换）
7 6 0 8 9（第4次比较：不交换）

参与比较的数据：7 6 0 8
第4次循环：
6 7 0 8（第1次比较：交换）
6 0 7 8（第2次比较：交换）
6 0 7 8（第3次比较：不交换）

参与比较的数据：6 0 7
第5次循环：
0 6 7（第1次比较：交换）
0 6 7（第2次比较：不交换）

参与比较的数据：0 6
第6次循环：
0 6 （第1次比较：不交换）

for(int i = 6; i > 0; i--){ // 6次
	//7条数据比6次
	//6条数据比5次
	//5条数据比4次
	//4条数据比3次
	//3条数据比2次
	//2条数据比1次
	for(int j = 0; j < i; j++){
	
	}
}

3、选择排序：
选择排序比冒泡排序的效率高。
高在交换位置的次数上。
选择排序的交换位置是有意义的。

循环一次，然后找出参加比较的这堆数据中最小的，拿着这个最小的值和
最前面的数据“交换位置”。


参与比较的数据：3 1 6 2 5 （这一堆参加比较的数据中最左边的元素下标是0）
第1次循环之后的结果是：
1 3 6 2 5 

参与比较的数据：3 6 2 5 （这一堆参加比较的数据中最左边的元素下标是1）
第2次循环之后的结果是：
2 6 3 5 

参与比较的数据：6 3 5 （这一堆参加比较的数据中最左边的元素下标是2）
第3次循环之后的结果是：
3 6 5 

参与比较的数据：6 5 （这一堆参加比较的数据中最左边的元素下标是3）
第4次循环之后的结果是：
5 6

注意：5条数据，循环4次。

4、二分法查找（折半查找）：
第一：二分法查找建立在排序的基础之上。
第二：二分法查找效率要高于“一个挨着一个”的这种查找方式。
第三：二分法查找原理？
	10(0下标) 23 56 89 100 111 222 235 500 600(下标9) arr数组
	
	目标：找出600的下标
		(0 + 9) / 2 --> 4（中间元素的下标）
	
	arr[4]这个元素就是中间元素：arr[4]是 100
	100 < 600
	说明被查找的元素在100的右边。
	那么此时开始下标变成：4 + 1

		(5 + 9) / 2 --> 7（中间元素的下标）
		arr[7] 对应的是：235
		235 < 600
		说明被查找的元素在235的右边。
	
	开始下标又进行了转变：7 + 1
		(8 + 9) / 2 --> 8
		arr[8] --> 500
		500 < 600
		开始元素的下标又发生了变化：8 + 1
		(9 + 9) / 2 --> 9
		arr[9]是600，正好和600相等，此时找到了。

5、介绍一下java.util.Arrays工具类。
所有方法都是静态的，直接用类名调用
主要使用的是两个方法：
	二分法查找，排序
以后要看文档，不要死记硬背。

原创老师链接
数组的算法
升序，引入一个工具

知识

如何导入工具类

import 工具类的路径




例子

import java.util.Arrays;



使用工具

sort方法

帮我们把数组进行升序，由小到大
会影响数组内部的结构


用法

Arrays.sort(数组);



参考代码
import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

        int[] nums = new int[]{2,5,3,2,6};

        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++){
            System.out.println(nums[i]);
        }
    }
}

交换两个变量
使用第三个变量

代码

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int a = 11;
        int b = 22;
        int temp;

        System.out.println("数据交换前a与b的值" + a + "---" + b);
        // 让临时的变量接收一个数据
        temp = b;
        b = a;
        a = temp;

        // 数据交换成功
        System.out.println("数据交换后a与b的值" + a + "---" + b);
    }
}



核心代码

temp = b;
b = a;
a = temp;

不允许使用第三个变量

核心代码

a=a+b; 
b=a-b;
a=a-b;

光标移动的最大下标算法

数组会在哪里停下，取决于数组的长度。
如果数组的长度是n，那么
下标不会走到n/2

算法代码
public class Test {
    public static void main(String[] args) {
        // 初始化一个数组
        String[] strList = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"};

        // 遍历时遇到哪个索引会停止的算法： 数组的长度除2取整
        int topIdx = strList.length / 2;

        // 开始遍历，让下标从0开始游走
        for (int i = 0; i < topIdx; i++) {
            // 把下标所在的值交给临时变量
            String temp = strList[i];
            // 获得交换索引值，计算出要与哪个索引进行数据交换
            int changeIndex = strList.length - 1 - i;
            // 把交换索引值，对应的数据赋值给当前光标所在空间
            strList[i] = strList[changeIndex];
            // 把临时变量的值，赋值给交换索引的值
            strList[changeIndex] = temp;
        }

        // 遍历数组，查看排序后的效果
        for (int j = 0; j < strList.length; j++) {
            System.out.print(strList[j]);
        }

    }
}


求最大值
算法

来一个临时变量
让数组成员的值与临时变量比较
谁大，就把谁的值赋给临时变量

代码
public class getmaxnum {
    public static void main(String[] args) {

        // 定义一个整数数组,同时给与初始值
        int[] numList = {11, 22, 4, 3, 55, 33};

        // 开始比较大小
        // 定义一个变量，用于保存最大的数据
        int temp = numList[0];

        // 开始鹿历
        for (int i = 1; i < numList.length; i++) {
            // 需要重复的事情就是
            // 拿temp的数据与下标所对应的数据进行大小比较，
            if (numList[i] > temp) {
                // 把当前下标对应的值，赋给temp变量
                temp = numList[i];
            }
        }

        System.out.println("最大的值是" + temp);
    }
}



追加数据
算法

遍历数组找到第一个出现null的位置
记录这个位置，并往数组的这个位置插入数据

代码
        String[] strList = new String[5];

        // 给空间赋值
        strList[0] = "hello";
        strList[1] = "java";
        strList[2] = "welcom";

        // 需要插入的数据
        String sendKey = "c#";

        // 插入算法
        for (int i = 0; i < strList.length; i++) {
            System.out.println(i);
            // 每一次进入循环要重复做的事情
            // 判断光标i所对应的值是否为null
            if (strList[i] == null) {
//                System.out.println("光标对应的值是null" + i);
                strList[i] = sendKey;
                break;
            }
        }

        for (int j = 0; j < strList.length; j++) {
            System.out.println(strList[j]);
        }


中部插入数据
伪代码
第一步：
找到最大有效数据的下标
int temp=0;
for(int m=0;m<数组.length;m++){
	if(数组[m]==null){
	temp = m;
	break;
}
temp--;

}

第二步：后移
// 数据后移的遍历
for(int i=temp;i>j;i--){
	数组[i+1]=数组[i];
}

第三步：
数据的插入
数组[j]=“html";

引言：
    笔者在学习Java数据结果跟算法的过程中，知道数组在数据结构跟算法中是很重要地存在，只有对数组有相当的认知以后才能说自己对这一模块才能说熟悉掌握，但凡在任何语言当中，学习用本质看现象才能更好的去解决更多的问题，也是走向更高的一层打下扎实的基础。
      那么我们说通过本质看现象是有相当的要求，不扯了。下面我们来看看Java数据结构当中的数组是怎么实现移除或者说删除数组元素的，在ArrayList当中是现在操作的，其中存在什么陷阱跟误解。
      数组在heap内存中是一段连续的空间，里面存放着相同的类型的元素 这个是我们在定义的时候指定的，我的猜测是做移除的时候 会重新定义一个新的内存空间，然后把当前这个数组的不为空的元素挨个盘的的存放进去，生成一个新的数组对象，然后把指针指向当前的这个数组对象（这即是Java的复制本质）。这样子做的好处是把没有用内存给清除掉，这也是为什么数组在删除元素的时候回比较慢的原因，只是引用的地址发生了改变，等待的即是GC来把这个源数组给回收。
    下面我们来看看实验：
class TestCopy{

    public static void main(String[] args) {

        Object[] src = {1,3,5,7,9,10,15,18};
        System.out.println(src.length);
        TestCopy.arrayCopy(src,4,src,3,4);

        for (int i = 0; i < src.length; i++) {
            System.out.print(src[i]+"\t");
        }
        System.out.println();
        System.out.println(src.length);
    }

    /**
     * 复制在Java中不一定是存在对象的丢失或者指向的改变
     * @param src
     * @param srcIndex
     * @param dest
     * @param destIndex
     */
    private static void arrayCopy(Object[] src,int srcIndex,Object[] dest,int destIndex,int length){
        for (int i = 0; i < length; i++) {
            dest[destIndex] = src[srcIndex];
            destIndex++;
            srcIndex++;
        }
        src[7] = null;
        System.gc();
    }
}
打印结果

上面这个只是对一个数组对象做复制的算法，不存在对象重新引用，其实这个就是ArraryList的remove的实现原理。这就是他为什么基于array来开发的，其实数组对象在初始化分配的时候他的长度就固定的（初始化给了值），他在内存在本身即是一段连续空间存在，remove方法只是把数组里面的内容移除，并不存在内存被回收的情况，所以里面的元素 就是我们经常说的size会发生改变，而length是不改变的，这本身就很客观，因为数组本身即是有一定容量的容器，有增有减。
我们来看看ArrayList的这个操作：

我上面做了一个实验，算法执行完以后  把最后一个值赋值为null，然后在做GC，但是控制台打印出来并没有回收这块内存
不过没有回收才是正常的，被回收的话那么则该对象的属性length就会发现变化 ，所以我对这个注释辨识持有怀疑。

全部章节   >>>>

//1.变量交换和数组的算法


变量交换

方法一，引用第三个变量




public class 方法一 {
	public static void main(String[]args){
		String a="a";
		String b="b";
		String temp;
		System.out.println("交换前a："+a+"\n交换前b："+b);
		temp=a;   //现在temp保存了a原来的值
		a=b;      //现在把b赋值给了a
		b=temp;   //现在把a原来的值给b
		System.out.println("交换后a："+a+"\n交换后b："+b);
	}
}

效果图：



方法二，求和


public class day9_03 {
	public static void main(String[]args){
		int a = 10;
		int b = 30;
		System.out.println("交换前a："+a+"\n交换前b："+b);
		a = b+a;   //现在a=10+30=40    b=30
		b = a-b;   //现在a=40    b=40-30=10
		a = a-b;   //现在a=40-10=30    b=10
		System.out.println("交换后a："+a+"\n交换后b："+b);
	}
}

效果图：




求最大值：


public class 求最大值 {
    public static void main(String[] args) {

        // 定义一个整数数组,同时给与初始值
        int[] numList = {11, 22, 4, 3, 64, 33};

        // 定义一个变量，用于保存最大的数据
        int temp = numList[0];

        // 开始遍历
        for (int i = 1; i < numList.length; i++) {
            // 需要重复的事情就是
            // 拿temp的数据与下标所对应的数据进行大小比较，
            if (numList[i] > temp) {
                // 把当前下标对应的值，赋给temp变量
                temp = numList[i];
            }
        }

        System.out.println("最大的值是" + temp);


    }
}



效果图


//2.数组的升序和降序


导包：import java.util.Arrays;


升序：Arrays.sort( 数组名称 );


代码
import java.util.Arrays;
public class day9_01 {
	public static void main(String[]args){
	
		// 定义一个整数数组,同时给与初始值
		int[] money={20,36,78,35,21,14,63};
		
		//从小到大排序
		Arrays.sort(money);  
		
		//遍历数组
		for(int i=0;i<money.length;i++){
			System.out.println(money[i]);   
		}
	}
}

效果图：




逆序：


代码

public class day9_04 {
	public static void main(String[] args) {
	
		//定义字符串数组，并给予A,B,C,D,E
		String[] sz={"A","B","C","D","E"};

		//遍历
		for(int i=0;i<sz.length;i++){
			System.out.println("逆序前："+sz[i]);
		}
		
		/*逆序
		原理：让下标第一位和倒数第一位交换，再让第二位和倒数第二位交换
		比如让A和E交换，再让B和D交换，使他们逆序。
		*/
		for(int i=0;i<sz.length/2;i++){
			String a=sz[i];
			sz[i]=sz[(sz.length)-1-i];
			sz[(sz.length)-1-i]=a;
		}
		
		//遍历
		for(int i=0;i<sz.length;i++){
			System.out.println("逆序后："+sz[i]);
		}
	}
}


效果图：




追加数据


代码

public class day9_08 {
	public static void main(String[] args) {
	
		//定义一个字符串数值
		String[] a=new String[5];
		
		//给空间赋值
		a[0]="hello";
		a[1]="java";
		a[2]="welcom";
		
		//需要插入的数据
		String b="html";

		//遍历找出空出的位置
		for(int i=0;i<a.length;i++){

			//每次遍历判断下标是不是null
			if(a[i]==null){
			//把需要插入的数据给空出来的位置
				a[i]=b;
				break;
			}
		}
		//遍历
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]);
		}
	}
}


效果图




中部插入数据


代码

public class day9_08 {
	public static void main(String[] args) {
	
		//定义一个字符串数值
		String[] a=new String[5];
		
		//给空间赋值
		a[0]="hello";
		a[1]="java";
		a[2]="welcom";

		//需要插入的数据
		String b="html";

		//遍历
		for(int q=0;q<a.length;q++){
			System.out.println("插入前："+a[q]);
		}

		//开始插入，遍历找出空的位置
		for(int i=0;i<a.length;i++){
			//每次遍历判断下标是不是null
			if(a[i]==null){
				//找出null，进入下一步，把数据往后移的遍历
				for(;0<=i;i--){
					//数据往后移
					int sz=i-1;
					a[i]=a[sz];
					
					
					//移了之后空出的位置
					if(sz==1){
						//插入数据并结束遍历
						a[sz]=b;
						break;
					}
				}
				break;
			}
		}

		//遍历
		for(int q=0;q<a.length;q++){
			System.out.println("插入后："+a[q]);
		}
	}
}


效果图