我是南城余！阿里云开发者平台专家博士证书获得者！
欢迎关注我的博客！一同成长！
一名从事运维开发的worker，记录分享学习。
专注于AI，运维开发，windows Linux 系统领域的分享！
本章节对应知识库
https://www.yuque.com/nanchengcyu/java
本内容来自尚硅谷课程，此处在知识库做了个人理解
————————————————
6. 数组的常见算法
6.1 数值型数组特征值统计
- 这里的特征值涉及到：平均值、最大值、最小值、总和等
**举例1：**数组统计：求总和、均值
public class TestArrayElementSum {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9};
//求总和、均值
int sum = 0;//因为0加上任何数都不影响结果
for(int i=0; i<arr.length; i++){
sum += arr[i];
}
double avg = (double)sum/arr.length;
System.out.println("sum = " + sum);
System.out.println("avg = " + avg);
}
}
**举例2：**求数组元素的总乘积
public class TestArrayElementMul {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9};
//求总乘积
long result = 1;//因为1乘以任何数都不影响结果
for(int i=0; i<arr.length; i++){
result *= arr[i];
}
System.out.println("result = " + result);
}
}
**举例3：**求数组元素中偶数的个数
public class TestArrayElementEvenCount {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9};
//统计偶数个数
int evenCount = 0;
for(int i=0; i<arr.length; i++){
if(arr[i]%2==0){
evenCount++;
}
}
System.out.println("evenCount = " + evenCount);
}
}
**举例4：**求数组元素的最大值
public class TestArrayMax {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9};
//找最大值
int max = arr[0];
for(int i=1; i<arr.length; i++){//此处i从1开始，是max不需要与arr[0]再比较一次了
if(arr[i] > max){
max = arr[i];
}
}
System.out.println("max = " + max);
}
}
**举例5：**找最值及其第一次出现的下标
public class TestMaxIndex {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9};
//找最大值以及第一个最大值下标
int max = arr[0];
int index = 0;
for(int i=1; i<arr.length; i++){
if(arr[i] > max){
max = arr[i];
index = i;
}
}
System.out.println("max = " + max);
System.out.println("index = " + index);
}
}
**举例6：**找最值及其所有最值的下标
public class Test13AllMaxIndex {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9,9,3};
//找最大值
int max = arr[0];
for(int i=1; i<arr.length; i++){
if(arr[i] > max){
max = arr[i];
}
}
System.out.println("最大值是：" + max);
System.out.print("最大值的下标有：");
//遍历数组，看哪些元素和最大值是一样的
for(int i=0; i<arr.length; i++){
if(max == arr[i]){
System.out.print(i+"\t");
}
}
System.out.println();
}
}
优化
public class Test13AllMaxIndex2 {
public static void main(String[] args) {
int[] arr = {4,5,6,1,9,9,3};
//找最大值
int max = arr[0];
String index = "0";
for(int i=1; i<arr.length; i++){
if(arr[i] > max){
max = arr[i];
index = i + "";
}else if(arr[i] == max){
index += "," + i;
}
}
System.out.println("最大值是" + max);
System.out.println("最大值的下标是[" + index+"]");
}
}
**举例7(难)：**输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如：输入的数组为1, -2, 3, -10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。
public class Test5 {
public static void main(String[] args) {
int[] arr = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
int i = getGreatestSum(arr);
System.out.println(i);
}
public static int getGreatestSum(int[] arr){
int greatestSum = 0;
if(arr == null || arr.length == 0){
return 0;
}
int temp = greatestSum;
for(int i = 0;i < arr.length;i++){
temp += arr[i];
if(temp < 0){
temp = 0;
}
if(temp > greatestSum){
greatestSum = temp;
}
}
if(greatestSum == 0){
greatestSum = arr[0];
for(int i = 1;i < arr.length;i++){
if(greatestSum < arr[i]){
greatestSum = arr[i];
}
}
}
return greatestSum;
}
}
举例8：评委打分
分析以下需求，并用代码实现：
（1）在编程竞赛中，有10位评委为参赛的选手打分，分数分别为：5，4，6，8，9，0，1，2，7，3
（2）求选手的最后得分（去掉一个最高分和一个最低分后其余8位评委打分的平均值）
/**
* @author 尚硅谷-宋红康
* @create 10:03
*/
public class ArrayExer {
public static void main(String[] args) {
int[] scores = {5,4,6,8,9,0,1,2,7,3};
int max = scores[0];
int min = scores[0];
int sum = 0;
for(int i = 0;i < scores.length;i++){
if(max < scores[i]){
max = scores[i];
}
if(min > scores[i]){
min = scores[i];
}
sum += scores[i];
}
double avg = (double)(sum - max - min) / (scores.length - 2);
System.out.println("选手去掉最高分和最低分之后的平均分为：" + avg);
}
}
6.2 数组元素的赋值与数组复制
**举例1：**杨辉三角（见二维数组课后案例）
**举例2：**使用简单数组
(1)创建一个名为ArrayTest的类，在main()方法中声明array1和array2两个变量，他们是int[]类型的数组。
(2)使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。
(3)显示array1的内容。
(4)赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)。打印出array1。 array2 = array1;
**思考：**array1和array2是什么关系？
**拓展：**修改题目，实现array2对array1数组的复制
**举例3：**一个数组，让数组的每个元素去除第一个元素，得到的商作为被除数所在位置的新值。
public class Test3 {
public static void main(String[] args) {
int[] arr = new int[]{12,43,65,3,-8,64,2};
// for(int i = 0;i < arr.length;i++){
// arr[i] = arr[i] / arr[0];
// }
for(int i = arr.length -1;i >= 0;i--){
arr[i] = arr[i] / arr[0];
}
//遍历arr
for(int i = 0;i < arr.length;i++){
System.out.print(arr[i] + " ");
}
}
}
**举例4：**创建一个长度为6的int型数组，要求数组元素的值都在1-30之间，且是随机赋值。同时，要求元素的值各不相同。
public class Test4 {
// 5-67 Math.random() * 63 + 5;
@Test
public void test1() {
int[] arr = new int[6];
for (int i = 0; i < arr.length; i++) {// [0,1) [0,30) [1,31)
arr[i] = (int) (Math.random() * 30) + 1;
boolean flag = false;
while (true) {
for (int j = 0; j < i; j++) {
if (arr[i] == arr[j]) {
flag = true;
break;
}
}
if (flag) {
arr[i] = (int) (Math.random() * 30) + 1;
flag = false;
continue;
}
break;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
//更优的方法
@Test
public void test2(){
int[] arr = new int[6];
for (int i = 0; i < arr.length; i++) {// [0,1) [0,30) [1,31)
arr[i] = (int) (Math.random() * 30) + 1;
for (int j = 0; j < i; j++) {
if (arr[i] == arr[j]) {
i--;
break;
}
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
**举例5：**扑克牌
案例：遍历扑克牌
遍历扑克牌，效果如图所示：
提示：使用两个字符串数组，分别保存花色和点数，再用一个字符串数组保存最后的扑克牌。
String[] hua = {“黑桃”,“红桃”,“梅花”,“方片”};
String[] dian = {“A”,“2”,“3”,“4”,“5”,“6”,“7”,“8”,“9”,“10”,“J”,“Q”,“K”};
package com.atguigu3.common_algorithm.exer5;
/**
* @author 尚硅谷-宋红康
* @create 17:16
*/
public class ArrayExer05 {
public static void main(String[] args) {
String[] hua = {"黑桃","红桃","梅花","方片"};
String[] dian = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
String[] pai = new String[hua.length * dian.length];
int k = 0;
for(int i = 0;i < hua.length;i++){
for(int j = 0;j < dian.length;j++){
pai[k++] = hua[i] + dian[j];
}
}
for (int i = 0; i < pai.length; i++) {
System.out.print(pai[i] + " ");
if(i % 13 == 12){
System.out.println();
}
}
}
}
拓展：在上述基础上，增加大王、小王。
**举例6：**回形数
从键盘输入一个整数（1~20） ，则以该数字为矩阵的大小，把1,2,3…n*n 的数字按照顺时针螺旋的形式填入其中。
例如： 输入数字2，则程序输出：
1 2
4 3
输入数字3，则程序输出：
1 2 3
8 9 4
7 6 5
输入数字4， 则程序输出：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
//方式1
public class RectangleTest {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("输入一个数字");
int len = scanner.nextInt();
int[][] arr = new int[len][len];
int s = len * len;
/*
* k = 1:向右
* k = 2:向下
* k = 3:向左
* k = 4:向上
*/
int k = 1;
int i = 0,j = 0;
for(int m = 1;m <= s;m++){
if(k == 1){
if(j < len && arr[i][j] == 0){
arr[i][j++] = m;
}else{
k = 2;
i++;
j--;
m--;
}
}else if(k == 2){
if(i < len && arr[i][j] == 0){
arr[i++][j] = m;
}else{
k = 3;
i--;
j--;
m--;
}
}else if(k == 3){
if(j >= 0 && arr[i][j] == 0){
arr[i][j--] = m;
}else{
k = 4;
i--;
j++;
m--;
}
}else if(k == 4){
if(i >= 0 && arr[i][j] == 0){
arr[i--][j] = m;
}else{
k = 1;
i++;
j++;
m--;
}
}
}
//遍历
for(int m = 0;m < arr.length;m++){
for(int n = 0;n < arr[m].length;n++){
System.out.print(arr[m][n] + "\t");
}
System.out.println();
}
}
}
//方式2
/*
01 02 03 04 05 06 07
24 25 26 27 28 29 08
23 40 41 42 43 30 09
22 39 48 49 44 31 10
21 38 47 46 45 32 11
20 37 36 35 34 33 12
19 18 17 16 15 14 13
*/
public class RectangleTest1 {
public static void main(String[] args) {
int n = 7;
int[][] arr = new int[n][n];
int count = 0; //要显示的数据
int maxX = n-1; //x轴的最大下标
int maxY = n-1; //Y轴的最大下标
int minX = 0; //x轴的最小下标
int minY = 0; //Y轴的最小下标
while(minX<=maxX) {
for(int x=minX;x<=maxX;x++) {
arr[minY][x] = ++count;
}
minY++;
for(int y=minY;y<=maxY;y++) {
arr[y][maxX] = ++count;
}
maxX--;
for(int x=maxX;x>=minX;x--) {
arr[maxY][x] = ++count;
}
maxY--;
for(int y=maxY;y>=minY;y--) {
arr[y][minX] = ++count;
}
minX++;
}
for(int i=0;i<arr.length;i++) {
for(int j=0;j<arr.length;j++) {
String space = (arr[i][j]+"").length()==1 ? "0":"";
System.out.print(space+arr[i][j]+" ");
}
System.out.println();
}
}
}
6.3 数组元素的反转
**实现思想：**数组对称位置的元素互换。
public class TestArrayReverse1 {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
System.out.println("反转之前：");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
//反转
/*
思路：首尾对应位置的元素交换
（1）确定交换几次
次数 = 数组.length / 2
（2）谁和谁交换
for(int i=0; i<次数; i++){
int temp = arr[i];
arr[i] = arr[arr.length-1-i];
arr[arr.length-1-i] = temp;
}
*/
for(int i=0; i<arr.length/2; i++){
int temp = arr[i];
arr[i] = arr[arr.length-1-i];
arr[arr.length-1-i] = temp;
}
System.out.println("反转之后：");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
或
public class TestArrayReverse2 {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5};
System.out.println("反转之前：");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
//反转
//左右对称位置交换
for(int left=0,right=arr.length-1; left<right; left++,right--){
//首 与 尾交换
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
System.out.println("反转之后：");
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
6.4 数组的扩容与缩容
数组的扩容
题目：现有数组 int[] arr = new int[]{1,2,3,4,5}; ，现将数组长度扩容1倍，并将10,20,30三个数据添加到arr数组中，如何操作？
public class ArrTest1 {
public static void main(String[] args) {
int[] arr = new int[]{1,2,3,4,5};
int[] newArr = new int[arr.length << 1];
for(int i = 0;i < arr.length;i++){
newArr[i] = arr[i];
}
newArr[arr.length] = 10;
newArr[arr.length + 1] = 20;
newArr[arr.length + 2] = 30;
arr = newArr;
//遍历arr
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
数组的缩容
题目：现有数组 int[] arr={1,2,3,4,5,6,7}。现需删除数组中索引为4的元素。
public class ArrTest2 {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
//删除数组中索引为4的元素
int delIndex = 4;
//方案1：
/*//创建新数组
int[] newArr = new int[arr.length - 1];
for (int i = 0; i < delIndex; i++) {
newArr[i] = arr[i];
}
for (int i = delIndex + 1; i < arr.length; i++) {
newArr[i - 1] = arr[i];
}
arr = newArr;
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}*/
//方案2：
for (int i = delIndex; i < arr.length - 1; i++) {
arr[i] = arr[i + 1];
}
arr[arr.length - 1] = 0;
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
6.5 数组的元素查找
1、顺序查找
顺序查找：挨个查看
要求：对数组元素的顺序没要求
public class TestArrayOrderSearch {
//查找value第一次在数组中出现的index
public static void main(String[] args){
int[] arr = {4,5,6,1,9};
int value = 1;
int index = -1;
for(int i=0; i<arr.length; i++){
if(arr[i] == value){
index = i;
break;
}
}
if(index==-1){
System.out.println(value + "不存在");
}else{
System.out.println(value + "的下标是" + index);
}
}
}
2、二分查找
举例：
实现步骤：
//二分法查找：要求此数组必须是有序的。
int[] arr3 = new int[]{-99,-54,-2,0,2,33,43,256,999};
boolean isFlag = true;
int value = 256;
//int value = 25;
int head = 0;//首索引位置
int end = arr3.length - 1;//尾索引位置
while(head <= end){
int middle = (head + end) / 2;
if(arr3[middle] == value){
System.out.println("找到指定的元素，索引为：" + middle);
isFlag = false;
break;
}else if(arr3[middle] > value){
end = middle - 1;
}else{//arr3[middle] < value
head = middle + 1;
}
}
if(isFlag){
System.out.println("未找打指定的元素");
}
6.6 数组元素排序
6.6.1 算法概述
-
定义
- 排序：假设含有n个记录的序列为{R1，R2，…,Rn},其相应的关键字序列为{K1，K2，…,Kn}。将这些记录重新排序为{Ri1,Ri2,…,Rin},使得相应的关键字值满足条Ki1<=Ki2<=…<=Kin,这样的一种操作称为排序。
- 通常来说，排序的目的是快速查找。
-
衡量排序算法的优劣：
-
时间复杂度：分析关键字的比较次数和记录的移动次数 -
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)<O(nn)
-
空间复杂度：分析排序算法中需要多少辅助内存一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。 -
稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。
-
6.6.2 排序算法概述
-
排序算法分类：内部排序和外部排序
内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。
-
十大内部排序算法
数组的排序算法很多，实现方式各不相同，时间复杂度、空间复杂度、稳定性也各不相同：
常见时间复杂度所消耗的时间从小到大排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
注意，经常将以2为底n的对数简写成logn。
6.6.3 冒泡排序（Bubble Sort）
排序思想：
-
比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
-
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
-
针对所有的元素重复以上的步骤，除了最后一个。
-
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。
**动态演示：**https://visualgo.net/zh/sorting
/*
1、冒泡排序（最经典）
思想：每一次比较“相邻（位置相邻）”元素，如果它们不符合目标顺序（例如：从小到大），
就交换它们，经过多轮比较，最终实现排序。
（例如：从小到大） 每一轮可以把最大的沉底，或最小的冒顶。
过程：arr{6,9,2,9,1} 目标：从小到大
第一轮：
第1次，arr[0]与arr[1]，6>9不成立，满足目标要求，不交换
第2次，arr[1]与arr[2]，9>2成立，不满足目标要求，交换arr[1]与arr[2] {6,2,9,9,1}
第3次，arr[2]与arr[3]，9>9不成立，满足目标要求，不交换
第4次，arr[3]与arr[4]，9>1成立，不满足目标要求，交换arr[3]与arr[4] {6,2,9,1,9}
第一轮所有元素{6,9,2,9,1}已经都参与了比较，结束。
第一轮的结果：第“一”最大值9沉底（本次是后面的9沉底），即到{6,2,9,1,9}元素的最右边
第二轮：
第1次，arr[0]与arr[1]，6>2成立，不满足目标要求，交换arr[0]与arr[1] {2,6,9,1,9}
第2次，arr[1]与arr[2]，6>9不成立，满足目标要求，不交换
第3次：arr[2]与arr[3]，9>1成立，不满足目标要求，交换arr[2]与arr[3] {2,6,1,9,9}
第二轮未排序的所有元素 {6,2,9,1}已经都参与了比较，结束。
第二轮的结果：第“二”最大值9沉底（本次是前面的9沉底），即到{2,6,1,9}元素的最右边
第三轮：
第1次，arr[0]与arr[1]，2>6不成立，满足目标要求，不交换
第2次，arr[1]与arr[2]，6>1成立，不满足目标要求，交换arr[1]与arr[2] {2,1,6,9,9}
第三轮未排序的所有元素{2,6,1}已经都参与了比较，结束。
第三轮的结果：第三最大值6沉底，即到 {2,1,6}元素的最右边
第四轮：
第1次，arr[0]与arr[1]，2>1成立，不满足目标要求，交换arr[0]与arr[1] {1,2,6,9,9}
第四轮未排序的所有元素{2,1}已经都参与了比较，结束。
第四轮的结果：第四最大值2沉底，即到{1,2}元素的最右边
*/
public class Test19BubbleSort{
public static void main(String[] args){
int[] arr = {6,9,2,9,1};
//目标：从小到大
//冒泡排序的轮数 = 元素的总个数 - 1
//轮数是多轮，每一轮比较的次数是多次，需要用到双重循环，即循环嵌套
//外循环控制 轮数，内循环控制每一轮的比较次数和过程
for(int i=1; i<arr.length; i++){ //循环次数是arr.length-1次/轮
/*
假设arr.length=5
i=1,第1轮，比较4次
arr[0]与arr[1]
arr[1]与arr[2]
arr[2]与arr[3]
arr[3]与arr[4]
arr[j]与arr[j+1]，int j=0;j<4; j++
i=2,第2轮，比较3次
arr[0]与arr[1]
arr[1]与arr[2]
arr[2]与arr[3]
arr[j]与arr[j+1]，int j=0;j<3; j++
i=3,第3轮，比较2次
arr[0]与arr[1]
arr[1]与arr[2]
arr[j]与arr[j+1]，int j=0;j<2; j++
i=4,第4轮，比较1次
arr[0]与arr[1]
arr[j]与arr[j+1]，int j=0;j<1; j++
int j=0; j<arr.length-i; j++
*/
for(int j=0; j<arr.length-i; j++){
//希望的是arr[j] < arr[j+1]
if(arr[j] > arr[j+1]){
//交换arr[j]与arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
//完成排序，遍历结果
for(int i=0; i<arr.length; i++){
System.out.print(arr[i]+" ");
}
}
}
冒泡排序优化（选讲）
/*
思考：冒泡排序是否可以优化
*/
class Test19BubbleSort2{
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
//从小到大排序
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;//假设数组已经是有序的
for (int j = 0; j < arr.length - 1 - i; j++) {
//希望的是arr[j] < arr[j+1]
if (arr[j] > arr[j + 1]) {
//交换arr[j]与arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;//如果元素发生了交换，那么说明数组还没有排好序
}
}
if (flag) {
break;
}
}
//完成排序，遍历结果
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
6.6.4 快速排序
快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一，是迄今为止所有内排序算法中速度最快的一种，快速排序的时间复杂度为O(nlog(n))。
快速排序通常明显比同为O(nlogn)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。
排序思想：
-
从数列中挑出一个元素，称为"基准"（pivot），
-
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
-
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
-
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
**动态演示：**https://visualgo.net/zh/sorting
图示1：
图示2：
第一轮操作：
第二轮操作：
6.6.5 内部排序性能比较与选择
-
性能比较
- 从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。
- 从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法。对于Shell排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。
- 从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序
- 从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。
-
选择
- 若n较小(如n≤50)，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。 - 若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；
- 若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
- 若n较小(如n≤50)，可采用直接插入或直接选择排序。
7. Arrays工具类的使用
java.util.Arrays类即为操作数组的工具类，包含了用来操作数组（比如排序和搜索）的各种方法。 比如：
数组元素拼接- static String toString(int[] a) ：字符串表示形式由数组的元素列表组成，括在方括号（“[]”）中。相邻元素用字符 ", "（逗号加空格）分隔。形式为：[元素1，元素2，元素3。。。]
- static String toString(Object[] a) ：字符串表示形式由数组的元素列表组成，括在方括号（“[]”）中。相邻元素用字符 ", "（逗号加空格）分隔。元素将自动调用自己从Object继承的toString方法将对象转为字符串进行拼接，如果没有重写，则返回类型@hash值，如果重写则按重写返回的字符串进行拼接。
数组排序- static void sort(int[] a) ：将a数组按照从小到大进行排序
- static void sort(int[] a, int fromIndex, int toIndex) ：将a数组的[fromIndex, toIndex)部分按照升序排列
- static void sort(Object[] a) ：根据元素的自然顺序对指定对象数组按升序进行排序。
- static void sort(T[] a, Comparator<? super T> c) ：根据指定比较器产生的顺序对指定对象数组进行排序。
数组元素的二分查找- static int binarySearch(int[] a, int key) 、static int binarySearch(Object[] a, Object key) ：要求数组有序，在数组中查找key是否存在，如果存在返回第一次找到的下标，不存在返回负数。
数组的复制- static int[] copyOf(int[] original, int newLength) ：根据original原数组复制一个长度为newLength的新数组，并返回新数组
- static T[] copyOf(T[] original,int newLength)：根据original原数组复制一个长度为newLength的新数组，并返回新数组
- static int[] copyOfRange(int[] original, int from, int to) ：复制original原数组的[from,to)构成新数组，并返回新数组
- static T[] copyOfRange(T[] original,int from,int to)：复制original原数组的[from,to)构成新数组，并返回新数组
比较两个数组是否相等- static boolean equals(int[] a, int[] a2) ：比较两个数组的长度、元素是否完全相同
- static boolean equals(Object[] a,Object[] a2)：比较两个数组的长度、元素是否完全相同
填充数组- static void fill(int[] a, int val) ：用val值填充整个a数组
- static void fill(Object[] a,Object val)：用val对象填充整个a数组
- static void fill(int[] a, int fromIndex, int toIndex, int val)：将a数组[fromIndex,toIndex)部分填充为val值
- static void fill(Object[] a, int fromIndex, int toIndex, Object val) ：将a数组[fromIndex,toIndex)部分填充为val对象
举例：java.util.Arrays类的sort()方法提供了数组元素排序功能：
import java.util.Arrays;
public class SortTest {
public static void main(String[] args) {
int[] arr = {3, 2, 5, 1, 6};
System.out.println("排序前" + Arrays.toString(arr));
Arrays.sort(arr);
System.out.println("排序后" + Arrays.toString(arr));
}
}
8. 数组中的常见异常
8.1 数组角标越界异常
当访问数组元素时，下标指定超出[0, 数组名.length-1]的范围时，就会报数组下标越界异常：ArrayIndexOutOfBoundsException。
public class TestArrayIndexOutOfBoundsException {
public static void main(String[] args) {
int[] arr = {1,2,3};
// System.out.println("最后一个元素：" + arr[3]);//错误，下标越界
// System.out.println("最后一个元素：" + arr[arr.length]);//错误，下标越界
System.out.println("最后一个元素：" + arr[arr.length-1]);//对
}
}
创建数组，赋值3个元素，数组的索引就是0，1，2，没有3索引，因此我们不能访问数组中不存在的索引，程序运行后，将会抛出 ArrayIndexOutOfBoundsException 数组越界异常。在开发中，数组的越界异常是不能出现的，一旦出现了，就必须要修改我们编写的代码。
8.2 空指针异常
观察一下代码，运行后会出现什么结果。
public class TestNullPointerException {
public static void main(String[] args) {
//定义数组
int[][] arr = new int[3][];
System.out.println(arr[0][0]);//NullPointerException
}
}
因为此时数组的每一行还未分配具体存储元素的空间，此时arr[0]是null，此时访问arr[0][0]会抛出NullPointerException 空指针异常。
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
空指针异常在内存图中的表现
小结：空指针异常情况
//举例一：
// int[] arr1 = new int[10];
// arr1 = null;
// System.out.println(arr1[9]);
//举例二：
// int[][] arr2 = new int[5][];
// //arr2[3] = new int[10];
// System.out.println(arr2[3][3]);
//举例三：
String[] arr3 = new String[10];
System.out.println(arr3[2].toString());
