数组概念
数组的相关概念和名词
1、数组(array)
数组(array)：简单的说，就是一组数, 一组具有相同数据类型的数，是按照一定顺序排列的集合。
当一组数据的数据类型，意义是一样的时候，那么为了方便的统一的管理它们，我们需要用新的数据的存储结构来进行存储。例如：数组。
所谓数组(Array)，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，以便统一管理他们，然后用编号区分他们，这个名字称为数组名，编号称为下标或索引(index)。
组成数组的各个变量称为数组的元素(element)。数组中元素的个数称为数组的长度(length)。
数组是一组具有相同数据类型的数据按照一定顺序排列的集合。
把有限的几个相同类型的变量使用一个名称来进行统一管理。
2、数组名
（1）这个数组名，代表的是一组数
（2）这个数组名中存储的整个数组的“首地址”
int[] scores = new int[3];
scores[0] = 100;
//数组名：例如：scores
3、下标(index)
我们使用编号、索引、下标来区别表示一组数当中某一个。
范围：[0,数组长度-1]
例如：遍历 for(int i = 0; i<arr.length; i++){}
int[] scores = new int[3];
scores[0] = 100;
//数组名：例如：scores
//下标：范围：[0,长度-1]
// 例如：[0]
4、元素(element)
这一组中的每一个数据都是元素。
如何表示数组元素？ 数组名[下标]
int[] scores = new int[3];
scores[0] = 100;
//数组名：例如：scores
//下标：范围：[0,长度-1]
// 例如：[0]
//元素：数组名[下标]
// 例如：scores[0]
5、数组的长度(length)
数组中元素的总个数。
如何获取数组长度？ 数组名.length
int[] scores = new int[3];
scores[0] = 100;
//数组名：例如：scores
//下标：范围：[0,长度-1]
// 例如：[0]
//元素：数组名[下标]
// 例如：scores[0]
//数组的长度：元素的总个数，可以这么表示： 数组名.length
数组、数组名、下标、元素、长度等名词了解就行，沟通的方便。
为什么要用数组呢？我用变量存储不香吗？
变量存储那么多不麻烦吗？声明、变量名、变量值，计算处理都不方便。
eg:
class Test01_Array{
public static void main(String[] args){
/*
要存储本组学员的成绩，例如：第1组，有5个同学
*/
/*
int score1 = 100;
int score2 = 90;
int score3 = 80;
int score4 = 70;
int score5 = 60;
//用5个变量存储没问题，但是如果涉及到对数据的管理：例如，求最值，排序等，就非常麻烦
*/
int[] scores = new int[5];//用scores这一个统一的名称，来管理5个int类型的元素
scores[0] = 100;//每一个元素都有自己的下标，编号，索引
scores[1] = 90;
scores[2] = 80;
scores[3] = 70;
scores[4] = 60;
// scores[6] = 50;// java.lang.ArrayIndexOutOfBoundsException:数组下标越界异常
System.out.println(scores.length);
for (int i = 0; i < scores.length; i++) {
System.out.print(scores[i] + "\t");
}
}
}
Result
5
100 90 80 70 60
Process finished with exit code 0
一维数组
创建数组（Java创建数组的方法大致有三种）
说明：这里以int为数据类型，以arr为数组名来演示
一、声明并赋值
int[] arr = {1,2,4, …};
注意这里的花括号不是语句块，而且而且花括号后的分号也不能省，…不是元素意思是可以指定多个元素。
二、声明数组名开辟空间并且赋值
int[] arr;
arr = new int[]{1,2,3, …};
三、声明数组时指定元素个数然后赋值
int[] arr1= new int[3];
注意:最大元素下标为2，并且所有的元素值均为0
赋值一般用for循环
四、在以上的基础上创建多维数组
int[][] arr = {{1,2,3},{4,5,6},{7,8,9}}; //每个子数组元素个数不要求均相同
int[][] arr = new int[m][n]; //其中n可以省略，在创建的时候可以指定
int[][][] arr = new int[m][n][q]; //同样其中n、q可以省略
总结
无论那种方法声明必须有 ：数据类型 [ ] ， 如：int[ ]
创建多维数组时，new后面的第一个方括号中的元素数量总不能省略
“new 数据类型[]{}”创建数组时，其中花括号可以省去，但要在“[ ]”中填写数组的个数
各个创建数组的方法使用演示
方法一：
int[] arr2 = {10,20,30};
for(int element:arr2) {
System.out.print(element+"\n");//其中 "\n" 是换行
}
输出结果：
10
20
30
方法二:
char[] arr4 ; //char型输入时要用单引号(')引着!
arr4 = new char[] {'a','b','c'};
for(char element:arr4) {
System.out.print(element + " ");
}
输出结果：
a b c
方法三：
int[] arr = new int[10];
//换成i<10 或i<=9 因为 arr[10]不存在 强行调用会出错（溢出）！
for(int i = 0;i<=9;i++) {
arr[i]=i;
System.out.print(arr[i]+" ");
}
输出结果：
0 1 2 3 4 5 6 7 8 9
方法四：
1.
int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};
矩阵形式输出为:
1 2 3
4 5 6
7 8 9
1.
int[][] arr = new int[m][n];
在赋值时使用for循环
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
arr[i][j] = int值;
}
}
若声明时省略n,赋值时须在内层循环中生成新一维数组
for(int i=0;i<m;i++){
arr[i] = new int[数量];
}
内容扩展
1.for each语句(增强性for循环)
用于对数组或实现Iterator接口的列表（ArrayList、LinkedList）集合(Set)等容器对象进行遍历。
格式：
for （数据类型 : emelent）{
System.out.println(emelent);
}
应用代码：
int[] arr2 = {10,20,30};
for(int element:arr2) {
System.out.print(element+"\n");
}
运行结果：
10
20
30
2.length属性 与 length（）方法
二者区别：
length属性是针对Java中的数组来说的，要求数组的长度可以用其length属性
length()方法是针对字符串来说的，要求一个字符串的长度就要用Java的length()方法
Java中的size()方法是针对泛型集合(Set)或列表(List)说的，如果想看这个泛型容器中有多少元素，就调用此方法
应用代码：
for(int i=0;i<arr5.length;i++) {
arr5[i]=i;
}
3.Arrays的toString方法
作用: 将数组的元素生成字符串，数组的各个元素使用方括号括着 [ ]
格式: Arrays.toString(数组名称)
注意: 此方法不能用于直接获得二维数组
应用代码：
int[] arr = {111,222,333};
System.out.println(Arrays.toString(arr));
运行结果：
[111, 222, 333]
遍历数组
题目描述
给一个数组：
int Arr[][]={{5,7,15},{8,4,11},{3,6,13}};
1
使用显示数组 for,for-each,和toString
1.for循环遍历
通常遍历数组都是使用for循环来实现。遍历一维数组很简单，遍历二维数组需要使用双层for循环，通过数组的length属性可获得数组的长度。
程序：
package 数组;
public class for遍历二维数组 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int Arr[][]={{5,7,15},{8,4,11},{3,6,13}};
for (int i = 0; i < Arr.length; i++) {
for (int j = 0; j < Arr[i].length; j++) {
System.out.print(Arr[i][j]+" ");
}
}
}
}
运行结果：
5 7 15 8 4 11 3 6 13
for循环本质就是把数组中的每个数据打印出来。
2.foreach语句遍历
遍历数组就是获取数组的每个元素。通常遍历数组都是使用for循环来实现的，但是for循环不够简洁，下面我们简要介绍一下使用foreach语句来实现遍历数组的方法。
java5之后，Java提供了一种更简洁的循环：foreach循环，这种循环遍历数组和集合更加简洁。使用foreach循环遍历数组时，无须获得数组和集合长度，无须根据索（下标）引来访问数组元素，foreach循环自动遍历数组和集合的每一个元素。
语法格式：
for(type element: array)
{
System.out.println(element);
}
注：
foreach 语句为数组或对象集合中的每个元素重复一个嵌入语句组。foreach 语句用于循环访问集合以获取所需信息，但不应用于更改集合内容以避免产生不可预知的副作用。
因此不要对foreach的循环变量赋值。
例如：
public static void main(String [] args){
int [] arr={1,2,3,4,5};
for(int a:arr){
a=0;
System.out.print(a);
}
System.out.print(“\n”+a[0]);
}
运行结果：
00000
1
从上面结果可以看出，由于在foreach循环中对数组进行赋值，结果导致不能正确遍历数组元素。而且当再次访问第一个数组元素时，发现数组元素依然没有改变。
程序：
package 数组;
public class foreach遍历二维数组 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int Arr[][]= {{5,7,15},{8,4,11},{3,6,13}};
System.out.println("数组中的元素是 ");
int i=0;
for(int x[]: Arr) {//行
i++;
int j=0;
for(int e:x) {//列
j++;
if(i==Arr.length&&j==x.length) {
System.out.print(e);//输出最后一个元素，后面不加逗号
}else
System.out.print(e+"、");
}
}
}
}
运行结果：
数组中的元素是
5、7、15、8、4、11、3、6、13
3.Arrays工具类中toString静态方法遍历
利用Arrays工具类中的toString静态方法可以将一维数组转化为字符串形式并输出。
已知打印一维数组的API为System.out.println ( Arrays.toString ();，其参数为数组名或数组指针，其支持的数据类型有很多，如：int[]、char[]、byte[]等。
3.1.程序
package 数组;
import java.util.Arrays;
public class toString遍历二维数组 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int Arr[][]={{5,7,15},{8,4,11},{3,6,13}};
System.out.println("Arr:"+Arrays.toString(Arr));
int b[][]={{5,7,15},{8,4,11},{3,6,13}};
System.out.println("Arr:"+Arrays.deepToString(b));
}
}
运行结果：
Arr:[[I@15db9742, [I@6d06d69c, [I@7852e922]
Arr:[[5, 7, 15], [8, 4,11], [3, 6, 13]]
注释：
注： *Arr:[[I@15db9742, [I@6d06d69c, [I@7852e922]*
这种输出结果是因为：Arr是一个二维数组。相当于一个长度为3的数组，但是这个数组的元素还是是数组。
当执行Arrays.toString的时候相当于遍历数组，并且输出数组的元素，但是这个数组的元素是数组，所以这里输出的是数组元素的地址。
3.2.Arrays.deepToString()与Arrays.toString()的区别
Arrays.deepToString()主要用于数组中还有数组的情况，而Arrays.toString()则相反，对于Arrays.toString()而言，当数组中有数组时，不会打印出数组中的内容，只会以地址的形式打印出来。
示例：
public class test {
public static void main(String[] args) {
int a[] = {1, 2, 3};
System.out.println(Arrays.toString(a));
int b[][] = {{1, 2, 3}, {4, 5, 6}};
System.out.println(Arrays.toString(b));
System.out.println(Arrays.deepToString(b));
}
}
结果：
[1, 2, 3]
[[I@14ae5a5, [I@7f31245a]
[[1, 2, 3], [4, 5, 6]]
3.3.Arrays 类
java.util.Arrays 类能方便地操作数组，它提供的所有方法都是静态的。
具有以下功能：
1.给数组赋值：通过 fill 方法。
2.对数组排序：通过 sort 方法,按升序。
3.比较数组：通过 equals 方法比较数组中元素值是否相等
4.查找数组元素：通过 binarySearch 方法能对排序好的数组进行二分查找法操作。
具体说明请查看下表：
| 序号 | 方法和说明 |
|---|---|
| 1 | public static int binarySearch(Object[] a, Object key)用二分查找算法在给定数组中搜索给定值的对象(Byte,Int,double等)。数组在调用前必须排序好的。如果查找值包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。 |
| 2 | public static boolean equals(long[] a, long[] a2)如果两个指定的 long 型数组彼此相等，则返回 true。如果两个数组包含相同数量的元素，并且两个数组中的所有相应元素对都是相等的，则认为这两个数组是相等的。换句话说，如果两个数组以相同顺序包含相同的元素，则两个数组是相等的。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。 |
| 3 | public static void fill(int[] a, int val)将指定的 int 值分配给指定 int 型数组指定范围中的每个元素。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。 |
| 4 | public static void sort(Object[] a)对指定对象数组根据其元素的自然顺序进行升序排列。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。 |
3.4. Java中对Array数组的常用操作
示例：
import java.util.*;
public class ArrayPrint {
public static void main(String[] args){
//声明数组
String [] arr;
int arr1[];
//初始化数组
int arr2[]=new int[]{1,2,3,4,5};
String[] array1={"马超","马云","关羽","刘备","张飞"};
String[] array2=new String[]{"黄渤","张艺兴","孙红雷","小猪","牙哥","黄磊"};
String[] array=new String[5];
//查看数组的长度
int length=array1.length;
System.out.println("length： "+array1.length);
//输出数组
System.out.println(array1); //结果：[Ljava.lang.String;@32f22097
System.out.println("arr2: "+Arrays.toString(arr2));
//遍历数组
for (int i = 0; i < array1.length; i++) {
System.out.println(array1[i]);
}
//int数组转成string数组
int[] array3={1,2,3,4,5,6,7,8,9,0};
String arrStrings=Arrays.toString(array3);
System.out.println("arrStrings:"+arrStrings);
//从array中创建arraylist
ArrayList <String> arrayList=new ArrayList<String>(Arrays.asList(array1));
System.out.println("arrayList:"+arrayList);
//数组中是否包含某一个值
String a="马超";
if (Arrays.asList(array1).contains(a)) {
System.out.println("马超在这里");
}
//将数组转成set集合
Set<String> set=new HashSet<String>(Arrays.asList(array2));
System.out.println("set:"+set);
//将数组转成list集合
List<String> list_1=new ArrayList<String>();
for (int i = 0; i < array2.length; i++) {
list_1.add(array2[i]);
}
System.out.println("list_1:"+list_1);
String[] arrStrings2={"1","2","3"};
List<String > list2=Arrays.asList(arrStrings2);
System.out.println("list2:"+list2);
//Arrays.fill()填充数组
int[] arr3=new int[5];
Arrays.fill(arr3, 10); //将数组全部填充10
System.out.println("arr3:"+arr3);
for (int i = 0; i < arr3.length; i++) {
System.out.println("arr3[i]:"+arr3[i]);
}
//数组排序
int[] arr4 = {3, 7, 2, 1, 9};
Arrays.sort(arr4);
System.out.println("arr4:"+arr4);
for (int i = 0; i < arr4.length; i++) {
System.out.println("arr4[i]:"+arr4[i]);
}
int[] arr5 = {3, 7, 2, 1, 9,3,45,7,8,8,3,2,65,34,5};
Arrays.sort(arr5, 1, 4); //从第几个到第几个之间的进行排序
for (int i = 0; i < arr5.length; i++) {
System.out.println("arr5[i]:"+arr5[i]);
}
//复制数组
int[] arr6 = {3, 7, 2, 1};
int[] arr7=Arrays.copyOf(arr6, 10); //指定新数组的长度
int[] arr8=Arrays.copyOfRange(arr6, 1, 3); //只复制从索引[1]到索引[3]之间的元素（不包括索引[3]的元素）
for (int i = 0; i < arr8.length; i++) {
System.out.println(arr8[i]);
}
//比较两个数组
int[] arr9 = {1, 2, 3, 4,5,6,7,8,9,0};
boolean arr10=Arrays.equals(arr6, arr9);
System.out.println(arr10);
//去重复
//利用set的特性
int[] arr11 = {1, 2, 3, 4,5,6,7,8,9,0,3,2,4,5,6,7,4,32,2,1,1,4,6,3};
Set<Integer> set2=new HashSet<Integer>();
for (int i = 0; i < arr11.length; i++) {
set2.add(arr11[i]);
}
System.out.println(set2);
int[] arr12 = new int[set2.size()];
int j=0;
for (Integer i:set2) {
arr12[j++]=i;
}
System.out.println(Arrays.toString(arr12));
}
}
打印结果：
打印结果：
length： 5
[Ljava.lang.String;@7852e922
arr2: [1, 2, 3, 4, 5]
马超
马云
关羽
刘备
张飞
arrStrings:[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
arrayList:[马超, 马云, 关羽, 刘备, 张飞]
马超在这里
set:[小猪, 牙哥, 黄渤, 黄磊, 孙红雷, 张艺兴]
list_1:[黄渤, 张艺兴, 孙红雷, 小猪, 牙哥, 黄磊]
list2:[1, 2, 3]
arr3:[I@4e25154f
arr3[i]:10
arr3[i]:10
arr3[i]:10
arr3[i]:10
arr3[i]:10
arr4:[I@70dea4e
arr4[i]:1
arr4[i]:2
arr4[i]:3
arr4[i]:7
arr4[i]:9
arr5[i]:3
arr5[i]:1
arr5[i]:2
arr5[i]:7
arr5[i]:9
arr5[i]:3
arr5[i]:45
arr5[i]:7
arr5[i]:8
arr5[i]:8
arr5[i]:3
arr5[i]:2
arr5[i]:65
arr5[i]:34
arr5[i]:5
7
2
false
[0, 32, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 32, 1, 2, 3, 4, 5, 6, 7, 8, 9]
数组的算法
排序算法
首先排序算法可以分为内部排序算法和外部排序算法：在内存中进行的称为内部排序算法，也就是这里所说的这十种算法；相应的，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序算法。接下来我们可用如下表来简单概括这十种算法：
| 十大经典排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O \OmicronO(n2) | O \OmicronO(n) | O \OmicronO(n2) | O \OmicronO(1) | In-place | 稳定 |
| 选择排序 | O \OmicronO(n2) | O \OmicronO(n2) | O \OmicronO(n2) | O \OmicronO(1) | In-place | 不稳定 |
| 插入排序 | O \OmicronO(n2) | O \OmicronO(n) | O \OmicronO(n2) | O \OmicronO(1) | In-place | 稳定 |
| 希尔排序 | O \OmicronO(n1.3) | O \OmicronO(n) | O \OmicronO(n2) | O \OmicronO(1) | In-place | 不稳定 |
| 归并排序 | O \OmicronO(nlog \loglog2n) | O \OmicronO(nlog \loglog2n) | O \OmicronO(nlog \loglog2n) | O \OmicronO(n) | Out-place | 稳定 |
| 快速排序 | O \OmicronO(nlog \loglog2n) | O \OmicronO(nlog \loglog2n) | O \OmicronO(n2) | O \OmicronO(log \loglog2n) | In-place | 不稳定 |
| 堆排序 | O \OmicronO(nlog \loglog2n) | O \OmicronO(nlog \loglog2n) | O \OmicronO(nlog \loglog2n) | O \OmicronO(1) | In-place | 不稳定 |
| 计数排序 | O \OmicronO(n+k) | O \OmicronO(n+k) | O \OmicronO(n+k) | O \OmicronO(k) | Out-place | 稳定 |
| 桶排序 | O \OmicronO(n+k) | O \OmicronO(n+k) | O \OmicronO(n2) | O \OmicronO(n+k) | Out-place | 稳定 |
| 基数排序 | O \OmicronO(n*k) | O \OmicronO(n*k) | O \OmicronO(n*k) | O \OmicronO(n+k) | Out-place | 稳定 |
表中数据说明：
- 稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
- 不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
- 时间复杂度： 描述一个算法执行所耗费的时间；
- 空间复杂度：描述一个算法执行所需内存的大小；
- n：数据规模；
- k：“桶”的个数；
- In-place：占用常数内存，不占用额外内存；
- Out-place：占用额外内存。
该十种排序算法可分为如下所示的两大类
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlog \loglogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
1、冒泡排序（Bubble Sort）
算法步驟
-
比较相邻的元素，如果第一个比第二个大，就交换它们两个；
-
对每一对相邻元素作同样的比价，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
-
针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；
-
重复步骤1~3，直到排序完成。
代码实现
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
boolean flag = true;
for (int j = 0; j < len - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) {
break;
}
}
}
}
2、选择排序（Selection Sort）
算法步驟
-
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
-
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
-
重复第2步，直到所有元素均排序完毕。
代码实现
public class SelectionSort {
public static void selectionSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int minVal = i;
for (int j = i + 1; j < len; j++) {
if (arr[minVal] > arr[j]) {
minVal = j;
}
}
if (minVal != i) {
int tmp = arr[i];
arr[i] = arr[minVal];
arr[minVal] = tmp;
}
}
}
}
3、插入排序（Insertion Sort）
算法步驟
-
首先从第一个元素开始，该元素被认为是有序的；
-
取出下一个元素，在已经排序的元素序列中从后往前进行扫描；
-
如果该已排好序的元素大于新元素，则将该元素移到下一位置；
-
重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；
-
将新元素插入到该位置后；
-
重复步骤2~5。
代码实现
public class InsertionSort {
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int val = arr[i], j = i;
while (j > 0 && val < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = val;
}
}
}
4、希尔排序（Shell Sort）
算法步驟
-
选择一个增量序列{t1, t2, …, tk}；
-
按增量序列个数k，对序列进行k趟排序；
-
每趟排序，根据对应的增量t，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
其中，增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, …, 1}，称为增量序列。一般的增量序列都选择以上说明的这个，但不一定是最优的。
代码实现
public class ShellSort {
public static void shellSort(int[] arr) {
int len = arr.length, tmp, j;
for (int gap = len / 2; gap >= 1; gap = gap / 2) {
for (int i = gap; i < len; i++) {
tmp = arr[i];
j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
}
}
}
5、归并排序（Merge Sort）
算法步驟
-
如果待排序列只有一个元素，则直接返回，否则将长度为n的待排序列分成两个长度为n/2的子序列，递归进行调用进行分割知道每个子序列中只有一个元素；
-
此时的每个子序列被认为是有序的，然后递归调用的返回子序列进行两两合并；
-
合并过程中完成排序操作，具体操作为设定两个指针，分别指向两个已经排序子序列的起始位置；
-
比较两个指针所指向的元素，选择相对小的元素放入到合并返回的数组，并移动指针到下一位置；
-
重复步骤3~4直到某一指针达到序列尾；
-
将另一序列剩下的所有元素直接复制到合并序列尾，最终得到的新序列就是有序序列。
代码实现
import java.util.Arrays;
public class MergeSort {
public static int[] mergeSort(int[] arr) {
int len = arr.length;
if (len < 2) {
return arr;
}
int mIdx = len / 2;
return merge(mergeSort(Arrays.copyOfRange(arr, 0, mIdx)), mergeSort(Arrays.copyOfRange(arr, mIdx, len)));
}
private static int[] merge(int[] arrLeft, int[] arrRight) {
int leftLen = arrLeft.length, rightLen = arrRight.length, leftIdx = 0, rightIdx = 0, idx = 0;
int[] result = new int[leftLen + rightLen];
while (leftIdx < leftLen && rightIdx < rightLen) {
if (arrLeft[leftIdx] < arrRight[rightIdx]) {
result[idx++] = arrLeft[leftIdx++];
} else {
result[idx++] = arrRight[rightIdx++];
}
}
while (leftIdx < leftLen) {
result[idx++] = arrLeft[leftIdx++];
}
while (rightIdx < rightLen) {
result[idx++] = arrRight[rightIdx++];
}
return result;
}
}
6、快速排序（Quick Sort）
算法步驟
-
从序列中随机挑出一个元素，做为基准（pivot，这里选择序列的最左边元素作为基准）；
-
重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面。该操作结束之后，该基准就处于数列的中间位置。这个操作称为分区（partition）；
-
递归地把小于基准值元素的子序列和大于基准值元素的子序列进行上述操作即可。
代码实现
public class QuickSort {
public static void quickSort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int left, int right) {
if (left < right) {
int pivotIdx = partition(arr, left, right);
sort(arr, 0, pivotIdx - 1);
sort(arr, pivotIdx + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int idx = left + 1;
for (int i = idx; i <= right; i++) {
if (arr[left] > arr[i]) {
swap(arr, i, idx++);
}
}
swap(arr, left, idx - 1);
return idx - 1;
}
private static void swap(int[] arr, int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
7、堆排序（Heap Sort）
算法步驟
-
将待排序列(R0, R1, ……, Rn)构建成最大堆（最小堆）；
-
将堆顶元素R[0]与最后一个元素R[n]进行交换，此时得到新的无序区(R0, R1, ……, Rn-1)和新的有序区(Rn),且满足R[0, 1, ……, n-1]<=R[n]（>=R[n]）；
-
由于调整后的新堆可能违反堆的性质，因此需要对当前无序区(R0, R1, ……, Rn-1)进行调整；
-
重复步骤2~3直到有序区的元素个数为n。
代码实现
public class HeapSort {
private static int heapLen;
public static void heapSort(int[] arr) {
heapLen = arr.length;
for (int i = heapLen - 1; i >= 0; i--) {
heapify(arr, i);
}
for (int i = heapLen - 1; i > 0; i--) {
swap(arr, 0, heapLen - 1);
heapLen--;
heapify(arr, 0);
}
}
private static void heapify(int[] arr, int idx) {
int left = idx * 2 + 1, right = idx * 2 + 2, largest = idx;
if (left < heapLen && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapLen && arr[right] > arr[largest]) {
largest = right;
}
if (largest != idx) {
swap(arr, largest, idx);
heapify(arr, largest);
}
}
private static void swap(int[] arr, int idx1, int idx2) {
int tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
}
8、计数排序（Counting Sort）
算法步驟
-
找出数组中的最大值maxVal和最小值minVal；
-
创建一个计数数组countArr，其长度是maxVal-minVal+1，元素默认值都为0；
-
遍历原数组arr中的元素arr[i]，以arr[i]-minVal作为countArr数组的索引，以arr[i]的值在arr中元素出现次数作为countArr[a[i]-min]的值；
-
遍历countArr数组，只要该数组的某一下标的值不为0则循环将下标值+minVal输出返回到原数组即可
代码实现
public class CountingSort {
public static void countingSort(int[] arr) {
int len = arr.length;
if (len < 2) return;
int minVal = arr[0], maxVal = arr[0];
for (int i = 1; i < len; i++) {
if (arr[i] < minVal) {
minVal = arr[i];
} else if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
int[] countArr = new int[maxVal - minVal + 1];
for (int val : arr) {
countArr[val - minVal]++;
}
for (int arrIdx = 0, countIdx = 0; countIdx < countArr.length; countIdx++) {
while (countArr[countIdx]-- > 0) {
arr[arrIdx++] = minVal + countIdx;
}
}
}
}
9、桶排序（Bucket Sort）
算法步驟
-
设置一个bucketSize（该数值的选择对性能至关重要，性能最好时每个桶都均匀放置所有数值，反之最差），表示每个桶最多能放置多少个数值；
-
遍历输入数据，并且把数据依次放到到对应的桶里去；
-
对每个非空的桶进行排序，可以使用其它排序方法（这里递归使用桶排序）；
-
从非空桶里把排好序的数据拼接起来即可。
代码实现
import java.util.ArrayList;
import java.util.List;
public class BucketSort {
private static List<Integer> bucketSort(List<Integer> arr, int bucketSize) {
int len = arr.size();
if (len < 2 || bucketSize == 0) {
return arr;
}
int minVal = arr.get(0), maxVal = arr.get(0);
for (int i = 1; i < len; i++) {
if (arr.get(i) < minVal) {
minVal = arr.get(i);
} else if (arr.get(i) > maxVal) {
maxVal = arr.get(i);
}
}
int bucketNum = (maxVal - minVal) / bucketSize + 1;
List<List<Integer>> bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>());
}
for (int val : arr) {
int idx = (val - minVal) / bucketSize;
bucket.get(idx).add(val);
}
for (int i = 0; i < bucketNum; i++) {
if (bucket.get(i).size() > 1) {
bucket.set(i, bucketSort(bucket.get(i), bucketSize / 2));
}
}
List<Integer> result = new ArrayList<>();
for (List<Integer> val : bucket) {
result.addAll(val);
}
return result;
}
}
10、基数排序（Radix Sort）
算法步骤
-
取得数组中的最大数，并取得位数，即为迭代次数n（例如：数组中最大数为123，则 n=3）；
-
arr为原始数组，从最低位（或最高位）开始根据每位的数字组成radix数组（radix数组是个二维数组，其中一维长度为10），例如123在第一轮时存放在下标为3的radix数组中；
-
将radix数组中的数据从0下标开始依次赋值给原数组；
-
重复2~3步骤n次即可。
代码实现
import java.util.ArrayList;
import java.util.List;
//基数排序
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr.length < 2) return;
int maxVal = arr[0];//求出最大值
for (int a : arr) {
if (maxVal < a) {
maxVal = a;
}
}
int n = 1;
while (maxVal / 10 != 0) {//求出最大值位数
maxVal /= 10;
n++;
}
for (int i = 0; i < n; i++) {
List<List<Integer>> radix = new ArrayList<>();
for (int j = 0; j < 10; j++) {
radix.add(new ArrayList<>());
}
int index;
for (int a : arr) {
index = (a / (int) Math.pow(10, i)) % 10;
radix.get(index).add(a);
}
index = 0;
for (List<Integer> list : radix) {
for (int a : list) {
arr[index++] = a;
}
}
}
}
}
11、总结
数据量规模较小，考虑插入或选择。当元素分布有序时插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用选择，效率略高于插入；
数据量规模中等，使用希尔排序；
数据量规模较大，考虑堆排序（元素分布接近正序或逆序）、快速排序（元素分布随机）和归并排序（稳定性）；
一般来说不使用冒泡。
多维数组
1 多维数组概述
Java 语言里提供了支持多维数组的语法。
如果说可以把一维数组当成几何中的线性图形， 那么二维数组就相当于是一个表格，像右图Excel 中的表格一样。
对于二维数组的理解，我们可以看成是一维数组 array1又作为另一个一维数组array2的元素而存 在。其实，从数组底层的运行机制来看，其实没有多维数组。
2 定义格式 二维数组[][]：数组中的数组
格式1（动态初始化）：int[][] arr = new int[3][2];
定义了名称为arr的二维数组
二维数组中有3个一维数组 每一个一维数组中有2个元素
一维数组的名称分别为arr[0], arr[1], arr[2]
给第一个一维数组1脚标位赋值为78写法是：arr[0][1] = 78;
格式2（动态初始化）：int[][] arr = new int[3][];
二维数组中有3个一维数组。
每个一维数组都是默认初始化值null (注意：区别于格式1）
可以对这个三个一维数组分别进行初始化 arr[0] = new int[3]; arr[1] = new int[1]; arr[2] = new int[2];
注： int[][]arr = new int[][3]; //非法
格式3（静态初始化）：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;
注意特殊写法情况：int[] x,y[]; x是一维数组，y是二维数组。
Java中多维数组不必都是规则矩阵形式
3.二分法查找算法
//二分法查找：要求此数组必须是有序的。
int[] arr3 = new int[]{-99,-54,-2,0,2,33,43,256,999};
boolean isFlag = true;
int number = 256;
//int number = 25;
int head = 0;//首索引位置
int end = arr3.length - 1;//尾索引位置
while(head <= end){
int middle = (head + end) / 2;
if(arr3[middle] == number){
System.out.println("找到指定的元素，索引为：" + middle);
isFlag = false; break; }else if(arr3[middle] > number){
end = middle - 1;
}else{//arr3[middle] < number
head = middle + 1;
}
}
if(isFlag){
System.out.println("未找打指定的元素");
}
4.冒泡排序
介绍： 冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元 素，如果他们的顺序错误就把他们交换过来。
排序思想：
-
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步 做完后，最后的元素会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要 比较为止。
public class BubbleSort {
public static void main(String[] args) {
int[] data = { 3, 1, 6, 2, 5 };
for (int i = data.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (data[j] > data[j + 1]) {
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}
5.快速排序
介绍： 快速排序通常明显比同为O(nlogn)的其他算法更快，因此常被采用，而且快 排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可 见掌握快排的重要性。
快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十 大算法之一，是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升 级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。
排序思想：
- 从数列中挑出一个元素，称为"基准"（pivot），
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准 值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后， 该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数 列排序。
- 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好 了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代 （iteration）中，它至少会把一个元素摆到它最后的位置去。
/**
* 快速排序
* @param array
*/
public static void quickSort(int[] array) {
int len;
if(array == null
|| (len = array.length) == 0
|| len == 1) {
return ;
}
sort(array, 0, len - 1);
}
/**
* 快排核心算法，递归实现
* @param array
* @param left
* @param right
*/
public static void sort(int[] array, int left, int right) {
if(left > right) {
return;
}
// base中存放基准数
int base = array[left];
int i = left, j = right;
while(i != j) {
// 顺序很重要，先从右边开始往左找，直到找到比base值小的数
while(array[j] >= base && i < j) {
j--;
}
// 再从左往右边找，直到找到比base值大的数
while(array[i] <= base && i < j) {
i++;
}
// 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
if(i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
// 将基准数放到中间的位置（基准数归位）
array[left] = array[i];
array[i] = base;
// 递归，继续向基准的左右两边执行和上面同样的操作
// i的索引处为上面已确定好的基准值的位置，无需再处理
sort(array, left, i - 1);
sort(array, i + 1, right);
}
6.选择排序
选择排序是一种简单直观的排序算法，工作原理为：在未排序的序列中找出最小(大)元素与第一个位置的元素交换位置
注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。
然后在剩下的元素中再找最小(大)元素与第二个元素的位置交换，依此类推，直到所有元素排序排序完成。根据上述描述，一共进行n-1趟比较后，就能完成整个排队过程。我们可以知道，第k趟比较需要进行的数组元素的两两比较的次数为n-k次，所以共需要的比较次数为n*(n-1) / 2，因此选择排序算法的时间复杂度与冒泡排序一样，也为O(n^2)。
算法简介：
1.初始状态：序列为无序状态。
2.第1次排序：从n个元素中找出最小(大)元素与第1个记录交换
3.第2次排序：从n-1个元素中找出最小(大)元素与第2个记录交换
4.第i次排序：从n-i+1个元素中找出最小(大)元素与第i个记录交换
5.以此类推直到排序完成
public class SelectSort {
public static void main(String[] args) {
int[] data = { 3, 1, 6, 2, 5 };
for (int i = 0; i < data.length; i++) {
int min = i;
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[min]) {
min = j;
}
}
// 进行位置的交换
if (min != i) {
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
}
7.插入排序
插入排序是一种简单直观的排序算法，工作原理为构建有序序列，对于未排序元素，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间，直到排序完成，如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。理解了插入排序的思想后，我们便能够得到它的时间复杂度。对于n个元素，一共需要进行n-1轮比较，而第k轮比较需要进行k次数组元素的两两比较，因此共需要进行的比较次数为：1 + 2 + … + (n-1)，所以插入排序的时间复杂度同冒泡排序一样，也为O(n^2)。
算法简介：
1.从第一个元素开始，该元素可认为已排序。
2.取出下一个元素，在排序好的元素序列中从后往前扫描
3.如果元素(已排序)大于新元素，将该元素移到下一位置
4.重复3.直到找到已排序的元素小于或等于新元素的位置
5.将新元素插入该位置后
6.重复2-5直到排序完成
public static void insertSort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
for (int j = i+1; j > 0; j--) {
if (a[j] < a[j - 1]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}else break;
}
}
}