java数组排序sort 七、Java数组

Java数组什么是数组

数组是相同类型数据的有序集合。
数组描述的是相同类型的若干个数据，按照一定的先后次序排列组合而成。
其中，每一个数据称作为一个数组元素，每个数组元素可以通过一个下标来访问它们。

数组声明创建数组声明创建

首先必须声明数组变量，才能在程序中使用数组。下面是声明数组变量的语法：

dataType[] arrayRefVar;//首选方法或dataType arrayRefVar[];//效果相同，单不是首选方法

Java语言使用new操作符来创建数组，语法如下

dataType[] arrayRefVar = new dataType[arraySize];演示（声明数组，创建数组，声明创建数组）：

package com.xiaodi.operator.array;public class ArrayDemo01 {public static void main(String[] args) {int[] nums; //声明一个数组nums = new int[10]; //创建一个数组 ， 表示的是能存放10个int类型的数据int[] nums1 = new int[10]; //声明创建 ， 表示的是能存放10个int类型的数据}}

数组的元素是通过索引访问的，数组索引从0开始。
获取数组长度：arrays.length

演示（给数组元素中赋值）：

package com.xiaodi.operator.array;public class ArrayDemo01 {public static void main(String[] args) {int[] nums; //声明一个数组nums = new int[10]; //创建一个数组//int[] nums1 = new int[10]; //声明创建//给数组元素中赋值nums[0] = 1;nums[1] = 2;nums[2] = 3;nums[3] = 4;nums[4] = 5;nums[5] = 6;nums[6] = 7;nums[7] = 8;nums[8] = 9;nums[9] = 10;//访问数组元素System.out.println(nums[8]); //返回9//没有赋值的话是有默认类型的 ， int类型的话0...(之前讲实例变量中有)System.out.println(nums[9]); //返回0}}

演示（计算数组所有元素的和）：

package com.xiaodi.operator.array;public class ArrayDemo02 {public static void main(String[] args) {//声明、创建int[] nums = new int[10];//赋值nums[0] = 1;nums[1] = 2;nums[2] = 3;nums[3] = 4;nums[4] = 5;nums[5] = 6;nums[6] = 7;nums[7] = 8;nums[8] = 9;nums[9] = 10;//计算数组中所有元素的和double sum = 0;for (int i = 0; i < nums.length; i++) {sum = sum + nums[i];}System.out.println("数组的和为："+sum);}}

这里需要学会的
创建和声明可以和成一句：
dataType[] arrayRefVar = new dataType[arraySize];还有通过下标访问元素，赋值：
//通过下标访问元素arrayRefVar[num];//赋值、需要注意的是类型需要一致arrayRefVar[num] = value;还有获取数组的长度：
arrayRefVar.length三种初始化静态初始化

//基本类型//创建+赋值 你放多少个他空间就是多大int[] a = {1, 2, 3};//引用类型后面会讲 ， 这里先不讲 ， 等一下看不懂增加了学习负担

动态初始化

//声明+创建 空间是自己定义的 ， 声明和创建好空间之后需要后期赋值//包含默认初始化 ， 就是如果没有进行赋值他默认的值是 ， 基本类型中除了布尔类型为false ， 其余默认值都为0int[] b = new int[10];b[0] = 1;

数组默认初始化

数组是引用类型，它的元素相当于类的实例变量，因此数组一经分配空间，其中的每个元素也被按照实例变量的方式被隐式初始化。

从内存分析帮助理解直接上图
Java内存图：

文章插图
声明和创建数组的时候Java内存是怎么做的：

文章插图
数组边界及小结数组的四个基本特点

其长度是确定的。数组一旦被创建，它的长度就是不可以改变的。
其元素必须是相同类型，不许出现混合类型
数组中的元素可以是任何数据类型，包括基本类型和引用类型
数组变量属于引用类型，数组也可以看成是对象，数组中的每个元素相当于该对象的成员变量。数组本身就是对象， Java中对象是在堆中的，因此数组无论保存原始类型还是其他对象类型，数组对象本身是在堆中的

数组边界

[0,length-1] ，如果越界就会报错；

public static void main(String[] args) {int[] a = new int[2];System.out.println(a[2]);}上面这段代码输出a[2]是会报下面这种错：
? ArryaIndexOutOfBoundsException：意思就是数组下标越界异常
小结

数组是相同数据类型(数据类型可以为任何类型)的有序集合
数组也是对象。数组元素相当于对象的成员变量
数组长度确定后，是不可变的。如果越界，则报错：ArryaIndexOutOfBoundsException

数组的使用*For-Each 循环例子(普通for循环)：

package com.xiaodi.operator.array;public class ArryaDemo03 {public static void main(String[] args) {//定义一个数组int[] arrays = {1, 2, 3, 4, 5, 6};//打印全部数组元素for (int i = 0; i < arrays.length; i++) {System.out.println(arrays[i]);}System.out.println("============================");//计算所有元素的和int sum = 0;for (int i = 0; i < arrays.length; i++) {sum += arrays[i];//sum = sum + arrays[i];}System.out.println(sum);System.out.println("============================");//查看元素中最大数int max = arrays[0];for (int i = 1; i < arrays.length; i++) {if (arrays[i] > max) {max = arrays[i];}}System.out.println("max："+max);}}

例子(增强型for循环)：

package com.xiaodi.operator.array;public class ArrayDemo04 {public static void main(String[] args) {//定义一个数组int[] arrays = {1, 2, 3, 4, 5, 6};//增强型for循环：JDK1.5新特性//省去下标 ， 0到srray.length-1 ， 依次遍历for (int array : arrays) {System.out.println(array);}}}

数组做方法的参数例子：

package com.xiaodi.operator.array;public class ArrayDemo04 {public static void main(String[] args) {//定义一个数组int[] arrays = {1, 2, 3, 4, 5, 6};//调用方法printArray(arrays);}//打印数组元素public static void printArray(int[] array) {for (int i = 0; i < array.length; i++) {System.out.println(array[i]);}}}

数组作返回值例子：

package com.xiaodi.operator.array;public class ArrayDemo04 {public static void main(String[] args) {//定义一个数组int[] arrays = {1, 2, 3, 4, 5, 6};//调用方法int[] reverseArray = reverse(arrays);//使用打印数组元素的方法去打印它printArray(reverseArray);}//打印数组元素public static void printArray(int[] array) {for (int i = 0; i < array.length; i++) {System.out.println(array[i]);}}//反转数组public static int[] reverse(int[] array) {int[] result = new int[array.length];for (int i = 0, j = result.length-1; i < result.length; i++,j--) {result[j] = array[i];}return result;}}

这题估计会难一点，不过花点时间去理解还是能学会的！
多维数组

多维数组可以看成是数组的数组，比如二维数组就是一个特殊的一维数组，其每一个元素都是一个一维数组。

二维数组声明创建

//动态初始化 声明+创建空间int[][] a = nwe int[2][5];//静态初始化 创建空间+赋值int[][] a = {{1,2},{3,4},{5,6},{7,8},{9,10}};

解析：以上二维数组a可以看成一个两行五列的数组
思考：多维数组的使用？
上例子：

package com.xiaodi.operator.array;public class ArrayDemo05 {public static void main(String[] args) {//[4][2]/*1,2array[0]3,4array[1]5,6array[2]7,8array[3]*/int[][] array = {{1,2},{3,4},{5,6},{7,8}};//输出array[0] ， 会输出一个对象 ， 我们现在看不懂// System.out.println(array[0]);//我们调用printArray这个方法就能打印出来printArray(array[0]);System.out.println("==============================================");//如果我们只需要array[0]的第一个元素 可以像下面这样写System.out.println(array[0][0]);System.out.println(array[0][1]);System.out.println("==============================================");//获取数组的长度System.out.println(array.length);//4System.out.println(array[0].length); //2System.out.println("==============================================");//根据这个 ， 我们就可以遍历这个二维数组里的所有元素了for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {System.out.println(array[i][j]);}}}//我们把上一段写的打印数组元素的方法拿过来//打印数组元素public static void printArray(int[] array) {for (int i = 0; i < array.length; i++) {System.out.println(array[i]);}}}

? 三维、四维、都是以此类推，不过我们二维数组已经够用了，而且用的不多，理解一下，知道有这个东西就行
Arrays 类（扩展）数组的工具类java.util.Arrays
由于数组对象本身并没有什么方法可以供我们调用，但API中提供了一个工具类Arrays供我们使用，从而可以对数据对象进行一些基本操作。
查看JDK帮助文档
Arrays类中的方法都是static修饰的静态方法，在使用的时候可以直接使用类名调用，而“不用”使用对象来调用(注意：是“不用”而不是“不能”)
Arrays类的打印数组元素的方法：

package com.xiaodi.operator.array;import java.util.Arrays;//引入Arrays类public class ArrayDemo06 {public static void main(String[] args) {int[] a = {1,2,3,546,123,4178,1222};System.out.println(a);//输出的不是我们想要的结果 是一个对象[I@1b6d3586System.out.println("===========================");//我们使用Arrays类的toString方法来试一下System.out.println(Arrays.toString(a));System.out.println("===========================");//这个方法我们也是可以自己实现的 ， 我想说的是这种方法也是人写的 ， 但是不建议重复造轮子；可以在IDEA上按住Ctrl键点击toString查看这个方法的源码printArray(a);}public static void printArray(int[] a) {for (int i = 0; i < a.length; i++) {if (i == 0) {System.out.print("[");}if (i == a.length-1) {System.out.print(a[i]+"]");}else {System.out.print(a[i]+", ");}}}}

Arrays类的排序方法：

package com.xiaodi.operator.array;import java.util.Arrays;//引入Arrays类public class ArrayDemo06 {public static void main(String[] args) {int[] a = {1,2,3,546,123,4178,1222};//对数组进行排序(升序)Arrays.sort(a);//使用toString输出看一下结果:[1, 2, 3, 123, 546, 1222, 4178]System.out.println(Arrays.toString(a));}}

Arrays具有一下常用功能

给数组赋值：通过 fill 方法
对数组排序：通过 sort 方法，升序
比较数组：通过 equals 方法比较数组中元素是否相等
查找数组元素：通过 binarySearch 方法能对排序好的数组进行二分查找法操作

我就不一一演示了，大家知道有这个工具类就行，如果要用到了再查官方文档，或者也可以自己写
冒泡排序（扩展）

冒泡排序无疑是最出名的排序算法之一，总共有8大排序！
冒泡的代码还是相当简单的，两层循环，外层冒泡轮数，里层依次比较，江湖中人人尽皆知

package com.xiaodi.operator.array;import java.util.Arrays;public class ArrayDemo07 {public static void main(String[] args) {int[] a= {1,5,2,8,23,15,992,563,123};//调用完我们自己写的排序方法后 ， 返回一个排序后的数组int[] sort = sort(a);System.out.println(Arrays.toString(sort));}//冒泡排序//1、比较数组中 ， 两个相邻的元素 ， 如果第一个数比第二个数大 ， 则就交换它们的位置//2、每一次比较 ， 都会产生一个最大 ， 或者最小的数字//3、下一轮则 ， 可以少一次排序//4、依次循环 ， 直到结束public static int[] sort(int[] array) {//临时变量int temp = 0;//外层循环 ， 判断我们循环要走多少次for (int i = 0; i < array.length; i++) {//内层循环 ， 比较判断两个数 ， 如果第一个数比第二个数大 ， 则交换位置for (int j = 0; j < array.length-1-i; j++) {if (array[j+1] < array[j]) {temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}return array;}}

结果：[1, 2, 5, 8, 15, 23, 123, 563, 992]
这个冒泡排序大家要闭着眼睛都会写

我们看到嵌套循环，应该立马就可以得出这个算法的时间复杂度为O(n2)（这个记一下就好）

思考(如果一开始就是拍好序了他是不是就没有必要去全部比较一轮了这样时间就浪费了)如何优化

package com.xiaodi.operator.array;import java.util.Arrays;public class ArrayDemo07 {public static void main(String[] args) {int[] a= {1,5,2,8,23,15,992,563,123};//调用完我们自己写的排序方法后 ， 返回一个排序后的数组int[] sort = sort(a);System.out.println(Arrays.toString(sort));}//冒泡排序//1、比较数组中 ， 两个相邻的元素 ， 如果第一个数比第二个数大 ， 则就交换它们的位置//2、每一次比较 ， 都会产生一个最大 ， 或者最小的数字//3、下一轮则 ， 可以少一次排序//4、依次循环 ， 直到结束public static int[] sort(int[] array) {//临时变量int temp = 0;//外层循环 ， 判断我们循环要走多少次for (int i = 0; i < array.length; i++) {boolean flag = false; //通过flag标识位减少没有意义的比较//内层循环 ， 比较判断两个数 ， 如果第一个数比第二个数大 ， 则交换位置for (int j = 0; j < array.length-1-i; j++) {if (array[j+1] < array[j]) {temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}if (flag == false) {break;}}return array;}}

稀疏数组（扩展）

需求：编写五子棋游戏中，有存盘退出和续上盘的功能

文章插图
分析问题：因为该二维数组是很多是默认值0 ，因此记录了很多没意义的数据
解决：稀疏数组
【java数组排序sort 七、Java数组】稀疏数组介绍

当一个数组中大部分元素为0 ，或者为同一值的数组时，可以使用稀疏数组来保存该数组
稀疏数组的处理方式是：
- 记录数组一共有几行几列，有多少个不同值
- 把具体不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模
如图下：左边是原始数组，右边是稀疏数组

文章插图
有6行， 7列，总共有8个值
第一个值在第0行第3列，值为22；通过坐标的方式定位
我们通过代码实现一下五子棋这个例子：

package com.xiaodi.operator.array;import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;public class ArrayDemo08 {public static void main(String[] args) {//1、创建一个二维数组 11*110：没有棋子1：黑棋子2：白棋子int[][] array1 = new int[11][11];array1[1][2] = 1;array1[2][3] = 2;//输出原始数组System.out.println("输出原始数组：");for (int[] ints : array1) {for (int anInt : ints) {System.out.print(anInt + "\t");}System.out.println();}System.out.println("--------------------------");//转换为稀疏数组来保存//1、获取有效值的个数int sum = 0;for (int i = 0; i < 11; i++) {for (int j = 0; j < 11; j++) {if (array1[i][j] != 0) {sum++;}}}System.out.println("有效值的个数：" + sum);System.out.println("--------------------------");//2、创建一个稀疏数组的数组int[][] array2 = new int[sum + 1][3];array2[0][0] = 11;array2[0][1] = 11;array2[0][2] = sum;//3、遍历二维数组 ， 将非零的值 ， 存放在稀疏数组里面int count = 0;for (int i = 0; i < array1.length; i++) {for (int j = 0; j < array1[i].length; j++) {if (array1[i][j] != 0) {count++;array2[count][0] = i;array2[count][1] = j;array2[count][2] = array1[i][j];}}}//4、输出稀疏数组System.out.println("输出稀疏数组：");for (int i = 0; i < array2.length; i++) {System.out.println(array2[i][0] + "\t"+ array2[i][1] + "\t"+ array2[i][2]);}System.out.println("稀疏数组还原：");//1、读取稀疏数组int[][] array3 = new int[array2[0][0]][array2[0][1]];for (int i = 1; i < array2.length; i++) {array3[array2[i][0]][array2[i][1]] = array2[i][2];}//输出还原后的数组System.out.println("输出还原后的数组：");for (int[] ints : array3) {for (int anInt : ints) {System.out.print(anInt + "\t");}System.out.println();}}}