数组的概述
数组(Array)，是多个相同类型数据按一定顺序排列 的集合，并使用一个名字命名，并通过编号的方式 对这些数据进行统一管理。数组是一种容器，可以同时存放多个数据值。
特点
- 数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括 基本数据类型和引用数据类型。但同一个数组只能是同一种类型
- 数组在内存方面存储的时候，数组中的元素内存地址(存储的每一个元素都是有规则的挨着排列的)是连续的。内存地址连续。这是数组存储元素的特点（特色）。数组实际上是一种简单的数据结构。
- 所有的数组都是拿“第一个小方框的内存地址”作为整个数组对象的内存地址。（数组中首元素的内存地址作为整个数组对象的内存地址。）
- 数组的长度一旦确定，就不能修改。
- 我们可以直接通过下标(或索引)的方式调用指定位置的元素，速度很快。
- 所有的数组对象都有length属性(java自带的)，用来获取数组中元素的个数。
- 数组元素是有下标（index）的，下标从 0 开始，也就是第一个元素的下标为 0，依次类推最后一个元素的下标为length - 1，我们可以通过数组的下标来访问数组的元素。
- 数组当中如果存储的是“java对象”的话，实际上存储的是对象的“引用（内存地址）”，数组中不能直接存储java对象。
数组的分类：
- 按照维度：一维数组、二维数组、三维数组、…（一维数组较多，二维数组偶尔使用！）
- 按照元素的数据类型分：基本数据类型元素的数组、引用数据类型元素的数组(即对 象数组)
数组这种数据结构的优点和缺点是什么？
优点：查询/查找/检索某个下标上的元素时效率极高。可以说是查询效率最高的一个数据结构。为什么检索效率高？
- 每一个元素的内存地址在空间存储上是连续的。
- 每一个元素类型相同，所以占用空间大小一样。
- 知道第一个元素内存地址，知道每一个元素占用空间的大小，又知道下标，所以通过一个数学表达式就可以计算出某个下标上元素的内存地址。直接通过内存地址定位元素，所以数组的检索效率是最高的。数组中存储100个元素，或者存储100万个元素，在元素查询/检索方面，效率是相同的，因为数组中元素查找的时候不会一个一个找，是通过数学表达式计算出来的。（算出一个内存地址，直接定位的。）
缺点：数组元素的增删效率低，数组不能存储大数据量。
- 由于为了保证数组中每个元素的内存地址连续，所以在数组上随机删除或者增加元素的时候，效率较低，因为随机增删元素会涉及到后面元素统一向前或者向后位移的操作。对于数组中最后一个元素的修改，是没有效率影响的。
- 因为很难在内存空间上找到一块特别大的连续的内存空间。
一维数组的声明格式有以下两种：
- 数组元素的类型[] 变量名称
- 数组元素的类型 变量名称[]
//数组的声明 int [] a; Student[] stu // 在一行中也可以声明多个数组，例如： int[] a, b, c
数组的初始化：在内存当中创建一个数组，并且向其中赋予一些默认值。
- 动态初始化（指定长度）：在创建数组的时候，直接指定数组当中的数据元素个数。
- 静态初始化（指定内容）：在创建数组的时候，不直接指定数据个数多少，而是直接将具体的数据内容进行指定。
静态初始化基本格式：
- 数据类型[] 数组名称 = new 数据类型[] { 元素1, 元素2, ... };
示例代码
// 直接创建一个数组，里面装的全都是int数字，具体为：5、15、25
int[] arrayA = new int[] { 5, 15, 25, 40 };
// 创建一个数组，用来装字符串："Hello"、"World"、"Java"
String[] arrayB = new String[] { "Hello", "World", "Java" };
静态初始化省略格式：
- 数据类型[] 数组名称 = { 元素1, 元素2, ... };
示例代码
// 省略格式的静态初始化
int[] arrayA = { 10, 20, 30 };
动态初始化数组的格式：
- 数据类型[] 数组名称 = new 数据类型[数组长度];
解析含义：
- 左侧数据类型：也就是数组当中保存的数据，全都是统一的什么类型
- 左侧的中括号：代表我是一个数组
- 左侧数组名称：给数组取一个名字
- 右侧的new：代表创建数组的动作
- 右侧数据类型：必须和左边的数据类型保持一致
- 右侧中括号的长度：也就是数组当中，到底可以保存多少个数据，是一个int数字
示例代码
package com.bjpowernode.javase.array;
/*
关于每个类型的默认值还有印象吗？
数据类型 默认值
----------------------------
byte 0
short 0
int 0
long 0L
float 0.0F
double 0.0
boolean false
char \u0000
引用数据类型 null
什么时候采用静态初始化方式，什么时候使用动态初始化方式呢？
当你创建数组的时候，确定数组中存储哪些具体的元素时，采用静态初始化方式。
当你创建数组的时候，不确定将来数组中存储哪些数据，你可以采用动态初始化的方式，预先分配内存空间。
*/
public class ArrayTest02 {
public static void main(String[] args) {
// 声明/定义一个数组，采用动态初始化的方式创建
int[] a = new int[4]; // 创建长度为4的int数组，数组中每个元素的默认值是0
// 遍历数组
for (int i = 0; i < a.length; i++) {
System.out.println("数组中下标为" + i + "的元素是：" + a[i]);
}
// 后期赋值
a[0] = 1;
a[1] = 100;
a[2] = 111;
a[3] = 222; // 注意下标别越界。
for (int i = 0; i < a.length; i++) {
System.out.println("数组中下标为" + i + "的元素是：" + a[i]);
}
// 初始化一个Object类型的数组，采用动态初始化方式
Object[] objs = new Object[3]; // 3个长度，动态初始化，所以每个元素默认值是null
for (int i = 0; i < objs.length; i++) {
System.out.println(objs[i]);
}
System.out.println("===============================");
String[] strs = new String[3];
for (int i = 0; i < strs.length; i++) {
System.out.println(strs[i]);
}
// 采用静态初始化的方式
String[] strs2 = {"abc", "def", "xyz"};
for (int i = 0; i < strs2.length; i++) {
System.out.println(strs2[i]);
}
// 存储Object，采用静态初始化呢？
/*Object o1 = new Object();
Object o2 = new Object();
Object o3 = new Object();
Object[] objects = {o1, o2, o3};*/
Object[] objects = {new Object(), new Object(), new Object()};
for (int i = 0; i < objects.length; i++) {
/*Object o = objects[i];
System.out.println(o);*/
System.out.println(objects[i]);
}
}
}
数组是引用类型，它的元素相当于类的成员变量，因此数组一经 分配空间，其中的每个元素也被按照成员变量同样的方式被隐式 初始化。不同数据类型的数组，默认值不同，具体如下所示
数组元素访问
数组遍历： 就是将数组中的每个元素分别获取出来，就是遍历。遍历也是数组操作中的基石
- 数组名 [ 索引 ]= 数值， 为数组中的元素赋值
- 变量= 数组名 [ 索引 ] ， 获取出数组中的元素
代码示例
package demo01;
public class ArrayTest01 {
public static void main(String[] args) {
// 声明一个int类型的数组，使用静态初始化的方式
int[] a = {1, 100, 10, 20, 55, 689};
// 这是C++风格，不建议java中使用。
//int a[] = {1, 100, 10, 20, 55, 689};
// 所有的数组对象都有length属性
System.out.println("数组中元素的个数" + a.length);
// 数组中每一个元素都有下标
// 通过下标对数组中的元素进行存和取。
// 取（读）
System.out.println("第一个元素 = " + a[0]);
System.out.println("最后一个元素 = " + a[5]);
System.out.println("最后一个元素 = " + a[a.length - 1]);
// 存（改）
// 把第一个元素修改为111
a[0] = 111;
// 把最后一个元素修改为0
a[a.length - 1] = 0;
System.out.println("第一个元素 = " + a[0]);
System.out.println("最后一个元素 = " + a[5]);
// 一维数组怎么遍历呢？
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]); // i是从0到5，是下标
}
// 下标为6表示第7个元素，第7个元素没有，下标越界了。会出现什么异常呢？
//System.out.println(a[6]); //ArrayIndexOutOfBoundsException（比较著名的异常。）
// 从最后一个元素遍历到第1个元素
for (int i = a.length - 1; i >= 0; i--) {
System.out.println("颠倒顺序输出-->" + a[i]);
}
}
}
数组越界异常
我们访问了数组中不存在的索引，程序运 行后，将会抛出 ArrayIndexOutOfBoundsException 数组越界异常。在开发中，数组的越界异常是不能出现的，一 旦出现了，就必须要修改我们编写的代码。
/*
数组的索引编号从0开始，一直到“数组的长度-1”为止。
如果访问数组元素的时候，索引编号并不存在，那么将会发生
数组索引越界异常
ArrayIndexOutOfBoundsException
原因：索引编号写错了。
解决：修改成为存在的正确索引编号。
*/
public class Demo01ArrayIndex {
public static void main(String[] args) {
int[] array = { 15, 25, 35 };
System.out.println(array[0]); //15
System.out.println(array[1]); // 25
System.out.println(array[2]); // 35
// 错误写法
// 并不存在3号元素，所以发生异常
System.out.println(array[3]);
}
}
数组空指针异常
数组变量名没有保存数组的内存地址，也就不允许再操作数组了，因此运行的时候 会抛出 NullPointerException 空指针异常。在开发中，数组的越界异常是不能出现的，一旦出现了，就必须要修 改我们编写的代码。
/*
所有的引用类型变量，都可以赋值为一个null值。但是代表其中什么都没有。
数组必须进行new初始化才能使用其中的元素。
如果只是赋值了一个null，没有进行new创建，
那么将会发生：
空指针异常 NullPointerException
原因：忘了new
解决：补上new
*/
public class Demo02ArrayNull {
public static void main(String[] args) {
int[] array = null;
// array = new int[3];
System.out.println(array[0]);
}
}
方法的参数类型是数组的时候
package demo01;
// 当一个方法上，参数的类型是一个数组的时候。
public class ArrayTest03 {
// main方法的编写方式，还可以采用C++的语法格式哦！
public static void main(String args[]) {
// 调用方法时传一个数组
int[] x = {1,2,3,4};
printArray(x);
// 创建String数组
String[] stringArray = {"abc", "def", "hehe", "haha"};
printArray(stringArray);
printArray( new String[10]); // 10个null
printArray(new int[4]);
}
public static void printArray(int[] array){
for(int i = 0; i < array.length; i++){
System.out.println(array[i]);
}
}
public static void printArray(String[] args){
for(int i = 0; i < args.length; i++){
System.out.println("String数组中的元素：" + args[i]);
}
}
}
main方法上面的“String[] args”有什么用？
JVM调用main方法的时候，会自动传一个String数组过来。JVM调用的时候一定会传一个String数组过来。默认情况，JVM传递过来的数组长度都是0，
// 以下这一行代码表示的含义：数组对象创建了，但是数组中没有任何数据。
String[] strs = new String[0];
String[] strs = {}; // 静态初始化数组，里面没东西。
其实这个数组是留给用户的，用户可以在控制台上输入参数，这个参数自动会被转换为“String[] args”。其实这个数组是留给用户的，用户可以在控制台上输入参数，这个参数自动会被转换为“String[] args”。例如这样运行程序：java ArrayTest05 abc def xyz，那么这个时候JVM会自动将“abc def xyz”通过空格的方式进行分离，分离完成之后，自动放到“String[] args”数组当中。所以main方法上面的String[] args数组主要是用来接收用户输入参数的。把abc def xyz 转换成字符串数组：{"abc","def","xyz"}
代码示例
package com.bjpowernode.javase.array;
/*
模拟一个系统，假设这个系统要使用，必须输入用户名和密码。
*/
public class ArrayTest06 {
// 用户名和密码输入到String[] args数组当中。
public static void main(String[] args) {
if(args.length != 2){
System.out.println("使用该系统时请输入程序参数，参数中包括用户名和密码信息，例如：zhangsan 123");
return;
}
// 程序执行到此处说明用户确实提供了用户名和密码。
// 接下来你应该判断用户名和密码是否正确。
// 取出用户名
String username = args[0];
// 取出密码
String password = args[1];
// 假设用户名是admin，密码是123的时候表示登录成功。其它一律失败。
// 判断两个字符串是否相等，需要使用equals方法。
//if(username.equals("admin") && password.equals("123")){
// 这样编写是不是可以避免空指针异常。
// 采用以下编码风格，及时username和password都是null，也不会出现空指针异常。（一条编程经验。）
if("admin".equals(username) && "123".equals(password)){
System.out.println("登录成功，欢迎[" + username + "]回来");
System.out.println("您可以继续使用该系统....");
}else{
System.out.println("验证失败，用户名不存在或者密码错误！");
}
}
}
数组引用类型深入理解
对于数组来说，实际上只能存储java对象的“内存地址”。数组中存储的每个元素是“引用”。
数组是父类型的时候，可以存储子类型的对象引用。
package demo01;
/**
* 一维数组的深入，数组中存储的类型为：引用数据类型
* 对于数组来说，实际上只能存储java对象的“内存地址”。数组中存储的每个元素是“引用”。
*/
public class ArrayTest {
public static void main(String[] args) {
// 创建一个Animal类型的数组，数组当中存储Cat和Bird
Cat c = new Cat();
Bird b = new Bird();
Animal[] anis = {c, b};
//Animal[] anis = {new Cat(), new Bird()}; // 该数组中存储了两个对象的内存地址。
for (int i = 0; i < anis.length; i++) {
// 这个取出来的可能是Cat，也可能是Bird，不过肯定是一个Animal
// 如果调用的方法是父类中存在的方法不需要向下转型。直接使用父类型引用调用即可。
Animal an = anis[i];
an.move();
//Animal中没有sing()方法。
//anis[i].sing();
// 调用子对象特有方法的话，需要向下转型！！！
if (anis[i] instanceof Cat) {
Cat cat = (Cat) anis[i];
cat.catchMouse();
} else if (anis[i] instanceof Bird) {
Bird bird = (Bird) anis[i];
bird.sing();
}
}
}
}
class Animal {
public void move() {
System.out.println("Animal move...");
}
}
// 商品类
class Product {
}
// Cat是子类
class Cat extends Animal {
public void move() {
System.out.println("猫在走猫步！");
}
// 特有方法
public void catchMouse() {
System.out.println("猫抓老鼠！");
}
}
// Bird子类
class Bird extends Animal {
public void move() {
System.out.println("Bird Fly!!!");
}
// 特有的方法
public void sing() {
System.out.println("鸟儿在歌唱！！！");
}
}
一维数组的扩容
数组扩容要使用System类中的arraycopy方法
- public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) ：将数组中指定的数据拷贝到另一个数组中。数组的拷贝动作是系统级的，性能很高。System.arraycopy方法具有5个参数，含义分别为：
代码示例
package demo01;
/**
* 关于一维数组的扩容。
* 在java开发中，数组长度一旦确定不可变，那么数组满了怎么办？
* 数组满了，需要扩容。
* java中对数组的扩容是：
* 先新建一个大容量的数组，然后将小容量数组中的数据一个一个拷贝到大数组当中。
* <p>
* 结论：数组扩容效率较低。因为涉及到拷贝的问题。所以在以后的开发中请注意：尽可能少的进行数组的拷贝。
* 可以在创建数组对象的时候预估计以下多长合适，最好预估准确，这样可以减少数组的扩容次数。提高效率。
*/
public class ArrayTest {
public static void main(String[] args) {
// java中的数组是怎么进行拷贝的呢？
//System.arraycopy(5个参数);
// 拷贝源（从这个数组中拷贝）
int[] src = {1, 11, 22, 3, 4};
// 拷贝目标（拷贝到这个目标数组上）
int[] dest = new int[20]; // 动态初始化一个长度为20的数组，每一个元素默认值0
// 调用JDK System类中的arraycopy方法，来完成数组的拷贝
System.arraycopy(src, 0, dest, 0, src.length);
for (int i = 0; i < dest.length; i++) {
System.out.println(dest[i]);
}
// 数组中如果存储的元素是引用，可以拷贝吗？当然可以。
// 拷贝的时候是拷贝对象，还是拷贝对象的地址。（地址。）
String[] strs = {"hello", "world!", "study", "java", "oracle", "mysql", "jdbc"};
String[] newStrs = new String[20];
System.arraycopy(strs, 0, newStrs, 0, strs.length);
for (int i = 0; i < newStrs.length; i++) {
System.out.println(newStrs[i]);
}
}
}
二维数组
二维数组的理解，我们可以看成是一维数组 array1又作为另一个一维数组array2的元素而存 在。其实，从数组底层的运行机制来看，其实没 有多维数组。当数组元素的类型是数组时就成了多维数组。
二维数组的初始化格式如下：
格式1：
- 数据类型[][] 数组名 = new 数据类型[二维数组的长度/包含的一维数组的个数][每个一维数组的长度];
class Demo01ArrayUse {
public static void main(String[] args) {
//定义了一个整型的二维数组，其中包含3个一维数组，每个一维数组可以存储5个整数
int[][] arr = new int[3][5];
//下标为0的位置上的一维数组
System.out.println(arr[0]);//[I@4554617c
//如果要获取具体的元素需要两个下标
System.out.println(arr[1][3]); //0
}
}
格式2：
- 数据类型[][] 数组名 = new 数据类型[二维数组的长度/包含的一维数组的个数][];
示例代码
class Demo01ArrayUse {
public static void main(String[] args) {
// 二维数组中有3个一维数组。每个一维数组都是默认初始化值null
int[][] arr = new int[3][];
//可以对这个三个一维数组分别进行初始化
arr[0] = new int[3];
arr[1] = new int[1];
arr[2] = new int[2];
//非法 int[][]arr = new int[][3];
//访问第一个一维数组的第2个元素
System.out.println(arr[0][1]);//0
//给此位置赋值
arr[0][1] = 52;
System.out.println(arr[0][1]);//52
}
}
格式3：
- 数据类型[][] 数组名 = {{元素},{元素1， 元素2},……};
示例代码
class Demo01ArrayUse {
public static void main(String[] args) {
int[][] arr = new int[][]{{3,8,2},{2,7},{9,0,1,6}};
/*
定义一个名称为arr的二维数组，二维数组中有三个一维数组
每一个一维数组中具体元素也都已初始化
第一个一维数组 arr[0] = {3,8,2};
第二个一维数组 arr[1] = {2,7};
第三个一维数组 arr[2] = {9,0,1,6};
第三个一维数组的长度表示方式：arr[2].length;
*/
}
}
二维数组中的length属性
// 二维数组
// 以下代码当中：里面的是4个一维数组。
int[][] a = {
{100, 200, 300},
{30, 20, 40, 50, 60},
{6, 7, 9, 1},
{0}
};
//获取二维数组中一维数组的个数
System.out.println(a.length); // 4
//获取二维数组中index为a[0]中一维数组中元素的个数
System.out.println(a[0].length); // 3
System.out.println(a[1].length); // 5
System.out.println(a[2].length); // 4
System.out.println(a[3].length); // 1
二维数组中元素的：读和改。
/*
关于二维数组中元素的：读和改。
a[二维数组中的一维数组的下标][一维数组的下标]
a[0][0]：表示第1个一维数组中的第1个元素。
a[3][100]：表示第4个一维数组中的第101个元素。
注意：对于a[3][100]来说，其中 a[3] 是一个整体。[100]是前面a[3]执行结束的结果然后再下标100.
*/
public class ArrayTest10 {
public static void main(String[] args) {
// 二维数组
int[][] a = {
{34,4,65},
{100,200,3900,111},
{0}
};
// 请取出以上二位数中的第1个一维数组的第一个元素。
System.out.println(a[0][0]);
// 取出第2个一维数组当中第3个元素
System.out.println("第二个一维数组中第三个元素：" + a[1][2]);
// 取出第3个一维数组当中第1个元素
System.out.println("第3个一维数组中第1个元素：" + a[2][0]);
// 改
a[2][0] = 11111;
System.out.println(a[2][0]);
// 注意别越界。
//java.lang.ArrayIndexOutOfBoundsException
//System.out.println(a[2][1]);
}
}
二维数组的遍历
package com.bjpowernode.javase.array;
/*
二维数组的遍历
*/
public class ArrayTest11 {
public static void main(String[] args) {
// 二维数组
String[][] array = {
{"java", "oracle", "c++", "python", "c#"},
{"张三", "李四", "王五"},
{"lucy", "jack", "rose"}
};
// 遍历二维数组，取出二维数组中有几个一维数组
for(int i = 0; i < array.length; i++){ // 外层循环3次。（负责纵向。）
// 负责遍历一维数组，取出每个一维数组中的具体元素
for(int j = 0; j < array[i].length; j++){
System.out.print(array[i][j] + " ");
}
// 输出换行符
System.out.println();
}
}
}
数组模拟栈
package com.bjpowernode.javase.array.homework;
/*
编写程序，使用一维数组，模拟栈数据结构。
要求：
1、这个栈可以存储java中的任何引用类型的数据。
2、在栈中提供push方法模拟压栈。（栈满了，要有提示信息。）
3、在栈中提供pop方法模拟弹栈。（栈空了，也有有提示信息。）
4、编写测试程序，new栈对象，调用push pop方法来模拟压栈弹栈的动作。
5、假设栈的默认初始化容量是10.（请注意无参数构造方法的编写方式。）
*/
public class MyStack {
// 向栈当中存储元素，我们这里使用一维数组模拟。存到栈中，就表示存储到数组中。
// 因为数组是我们学习java的第一个容器。
// 为什么选择Object类型数组？因为这个栈可以存储java中的任何引用类型的数据
// new Animal()对象可以放进去，new Person()对象也可以放进去。因为Animal和Person的超级父类就是Object。
// 包括String也可以存储进去。因为String父类也是Object。
private Object[] elements;
// 栈帧，永远指向栈顶部元素
// 那么这个默认初始值应该是多少。注意：最初的栈是空的，一个元素都没有。
//private int index = 0; // 如果index采用0，表示栈帧指向了顶部元素的上方。
//private int index = -1; // 如果index采用-1，表示栈帧指向了顶部元素。
private int index;
/**
* 无参数构造方法。默认初始化栈容量10.
*/
public MyStack() {
// 一维数组动态初始化
// 默认初始化容量是10.
this.elements = new Object[10];
// 给index初始化
this.index = -1;
}
/**
* 压栈的方法
* @param obj 被压入的元素
*/
public void push(Object obj){
if(index >= elements.length - 1){
System.out.println("压栈失败，栈已满！");
return;
}
// 程序能够走到这里，说明栈没满
// 向栈中加1个元素，栈帧向上移动一个位置。
index++;
elements[index] = obj;
// 在声明一次：所有的System.out.println()方法执行时，如果输出引用的话，自动调用引用的toString()方法。
System.out.println("压栈" + obj + "元素成功，栈帧指向" + index);
}
/**
* 弹栈的方法，从数组中往外取元素。每取出一个元素，栈帧向下移动一位。
* @return
*/
public void pop(){
if(index < 0){
System.out.println("弹栈失败，栈已空！");
return;
}
// 程序能够执行到此处说明栈没有空。
System.out.print("弹栈" + elements[index] + "元素成功，");
// 栈帧向下移动一位。
index--;
System.out.println("栈帧指向" + index);
}
// set和get也许用不上，但是你必须写上，这是规矩。你使用IDEA生成就行了。
// 封装：第一步：属性私有化，第二步：对外提供set和get方法。
public Object[] getElements() {
return elements;
}
public void setElements(Object[] elements) {
this.elements = elements;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
Arrays工具类
java.util.Arrays类即为操作数组的工具类，包含了用来操作数组（比 如排序和搜索）的各种方法。
数组中常用的算法
冒泡排序
package com.bjpowernode.javase.array;
/*
冒泡排序算法
1、每一次循环结束之后，都要找出最大的数据，放到参与比较的这堆数据的最右边。（冒出最大的那个气泡。）
2、核心：
拿着左边的数字和右边的数字比对，当左边 > 右边的时候，交换位置。
原始数据：
3, 2, 7, 6, 8
第1次循环：(最大的跑到最右边。)
2, 3, 7, 6, 8 （3和2比较，2 < 3，所以2和3交换位置）
2, 3, 7, 6, 8 （虽然不需要交换位置：但是3和7还是需要比较一次。）
2, 3, 6, 7, 8 （7和6交换位置）
2, 3, 6, 7, 8 （虽然不需要交换位置：但是3和7还是需要比较一次。）
经过第1次循环，此时剩下参与比较的数据：2, 3, 6, 7
第2次循环：
2, 3, 6, 7 (2和3比较，不需要交换位置)
2, 3, 6, 7 （3和6比较，不需要交换位置）
2, 3, 6, 7 (6和7比较，不需要交换位置)
经过第2次循环，此时剩下参与比较的数据：2, 3, 6
第3次循环：
2, 3, 6 (2和3比较，不需要交换位置)
2, 3, 6 （3和6比较，不需要交换位置）
经过第3次循环，此时剩下参与比较的数据：2, 3
第4次循环：
2, 3 (2和3比较，不需要交换位置)
*/
public class BubbleSort {
public static void main(String[] args) {
// 这是int类型的数组对象
//int[] arr = {3, 2, 7, 6, 8};
int[] arr = {9, 8, 10, 7, 6, 0, 11};
// 经过冒泡排序算法对以上数组中元素进行排序
// 冒泡排序算法的核心是什么？
// 7条数据，循环6次。以下的代码可以循环6次。（冒泡排序的外层循环采用这种方式）
//int count = 0;
int count2 = 0;
for(int i = arr.length-1; i > 0; i--){
for(int j = 0; j < i; j++){
// 不管是否需要交换位置，总之是要比较一次的。
//count++;
if(arr[j] > arr[j+1]){
// 交换位置。
// arr[j] 和 arr[j+1] 交换
int temp;
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
count2++;
}
}
}
//System.out.println("比较次数：" + count);
System.out.println("交换位置的次数：" + count2); //13
// 输出结果
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
选择排序算法
package com.bjpowernode.javase.array;
/*
选择排序：
每一次从这堆“参与比较的数据当中”找出最小值，
拿着这个最小值和“参与比较的这堆最前面的元素”交换位置。
选择排序比冒泡排序好在：每一次的交换位置都是有意义的。
关键点：选择排序中的关键在于，你怎么找出一堆数据中最小的。
3 2 6 1 5
假设：
第一个3是最小的。
3和2比较，发现2更小，所以此时最小的是2.
继续拿着2往下比对，2和6比较，2仍然是最小的。
继续拿着2往下比对，2和1比对，发现1更小，所以此时最小的是1.
继续拿着1往下比对，1和5比对，发现1还是小的，所以1就是最小的。
拿着1和最左边的3交换位置。
2 6 3 5
假设：
第一个2是最小的。
...
6 3 5
假设6是最小的：
6和3比对，发现3更小，所以此时最小的是3.
...
*/
public class SelectSort {
public static void main(String[] args) {
//int[] arr = {3, 1, 6, 2, 5};
int[] arr = {9, 8, 10, 7, 6, 0, 11};
int count = 0;
int count2 = 0;
// 选择排序
// 5条数据循环4次。（外层循环4次。）
for(int i = 0; i < arr.length - 1; i++){
// i的值是0 1 2 3
// i正好是“参加比较的这堆数据中”最左边那个元素的下标。
//System.out.println(i);
// i是一个参与比较的这堆数据中的起点下标。
// 假设起点i下标位置上的元素是最小的。
int min = i;
for(int j = i+1; j < arr.length; j++){
count++;
//System.out.println("===>" + j);
if(arr[j] < arr[min]){
min = j; //最小值的元素下标是j
}
}
// 当i和min相等时，表示最初猜测是对的。
// 当i和min不相等时，表示最初猜测是错的，有比这个元素更小的元素，
// 需要拿着这个更小的元素和最左边的元素交换位置。
if(min != i){
// 表示存在更小的数据
// arr[min] 最小的数据
// arr[i] 最前面的数据
int temp;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
count2++;
}
}
// 冒泡排序和选择排序实际上比较的次数没变。
// 交换位置的次数减少了。
System.out.println("比较次数" + count); // 21
System.out.println("交换次数：" + count2); // 5
// 排序之后遍历
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
//1 2 3 4 5
//假设1是最小的，结果1确实是最小的，就不需要交换位置。
二分法排序
package com.bjpowernode.javase.array;
/*
1、数组工具类：自己写的。不是SUN的。
2、关于查找算法中的：二分法查找。
10(下标0) 11 12 13 14 15 16 17 18 19 20(下标10) arr数组。
通过二分法查找，找出18这个元素的下标：
(0 + 10) / 2 --> 中间元素的下标： 5
拿着中间这个元素和目标要查找的元素进行对比：
中间元素是：arr[5] --> 15
15 < 18(被查找的元素)
被查找的元素18在目前中间元素15的右边。
所以开始元素的下标从0变成 5 + 1.
再重新计算一个中间元素的下标：
开始下标是：5 + 1
结束下标是：10
(6 + 10) / 2 --> 8
8下标对应的元素arr[8]是18
找到的中间元素正好和被找的的元素18相等，表示找到了：下标为8
二分法查找的终止条件：一直折半，直到中间的那个元素恰好是被查找的元素。
3、二分法查找算法是基于排序的基础之上。（没有排序的数据是无法查找的。）
*/
public class ArrayUtil {
public static void main(String[] args) {
int[] arr = {100,200,230,235,600,1000,2000,9999};
// 找出arr这个数组中200所在的下标。
// 调用方法
int index = binarySearch(arr, 230);
System.out.println(index == -1 ? "该元素不存在！" : "该元素下标" + index);
}
/**
* 从数组中查找目标元素的下标。
* @param arr 被查找的数组（这个必须是已经排序的。）
* @param dest 目标元素
* @return -1表示该元素不存在，其它表示返回该元素的下标。
*/
public static int binarySearch(int[] arr, int dest) {
// 开始下标
int begin = 0;
// 结束下标
int end = arr.length - 1;
// 开始元素的下标只要在结束元素下标的左边，就有机会继续循环。
while(begin <= end) {
// 中间元素下标
int mid = (begin + end) / 2;
if (arr[mid] == dest) {
return mid;
} else if (arr[mid] < dest) {
// 目标在“中间”的右边
// 开始元素下标需要发生变化（开始元素的下标需要重新赋值）
begin = mid + 1; // 一直增
} else {
// arr[mid] > dest
// 目标在“中间”的左边
// 修改结束元素的下标
end = mid - 1; // 一直减
}
}
return -1;
}
}