第二章 數組
1、數組的概述
/*
* 一、數組的概述
* 1.數組的了解：數組(Array)，是多個相同類型資料按一定順序排列的集合，
* 并使用一個名字命名，并通過編号的方式對這些資料進行統一管理。
*
* 2.數組的相關概念：
* >數組名
* >元素
* >角标、下标、索引
* >數組的長度：元素的個數
*
* 3.數組的特點：
* 1)數組屬于引用類型的變量。數組的元素，既可以是基本資料類型，也可以是引用資料類型。
* 2)建立數組對象會在記憶體中開辟一整塊連續的空間；
* 3)數組的長度一旦确定，就不能修改;
* 4)數組是有序排列的。
*
* 4.數組的分類：
* ① 按照維數：一維數組、二維數組、三維數組……
* ② 按照數組元素類型：基本資料類型元素的數組、引用類型元素的數組
*
*/ 2、一維數組的使用
/*
* ① 一維數組的聲明和初始化
* ② 如何調用數組的指定位置的元素
* ③ 如何擷取數組的長度
* ④ 如何周遊數組
* ⑤ 數組元素的預設初始化值：見ArrayTest1.java
* ⑥ 數組的記憶體解析：見ArrayTest1.java
*/ 代碼案例1——ArrayTest.java
public class ArrayTest {
public static void main(String[] args) {
//1.一維數組的聲明和初始化
int num; //聲明
num = 10; //初始化
int id = 1001; //聲明 + 初始化
int[] ids; //聲明
//1.1靜态初始化:數組的初始化和數組元素的指派操作，同時進行
ids = new int[]{1001, 1002, 1003, 1004};
//1.2動态初始化:數組的初始化和數組元素的指派操作，分開進行
String[] names = new String[5];
//錯誤的寫法：
// int[] arr1 = new int[]; // 未指派，未指明長度
// int[5] arr2 = new int[5];
// int[] arr3 = new int[3]{1,2,3};
//也是正确的寫法：
int[] arr4 = {1, 2, 3, 4, 5}; //類型推斷
//總結：數組一旦初始化完成，其長度就确定了
//2.如何調用數組的指定位置的元素:通過角标的方法調用
//數組的角标（或索引）從0開始，到數組的長度-1結束
names[0] = "王銘";
names[1] = "王赫";
names[2] = "張學良";
names[3] = "孫居龍";
names[4] = "小明";
// names[5] = "周揚";
//3.如何擷取數組的長度。
//屬性：length
System.out.println(names.length); // 5
System.out.println(ids.length); // 4
//4.如何周遊數組
// System.out.println(names[0]);
// System.out.println(names[1]);
// System.out.println(names[2]);
// System.out.println(names[3]);
// System.out.println(names[4]);
for (int i = 0; i < names.length; i++) {
System.out.print(names[i] + " ");
}
}
} 代碼案例2——ArrayTest1.java
/*
* 5.數組元素的預設初始化值
* > 數組元素是整型：0
* > 數組元素是浮點型：0.0
* > 數組元素是char型：0 或 '\u0000',而非 '0'
* > 數組元素是boolean型：false
*
* > 數組元素是引用資料類型：null
*
* 6.數組的記憶體解析
*/
public class ArrayTest1 {
public static void main(String[] args) {
//5.數組元素的預設初始化值
int[] arr = new int[4];
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
System.out.println("************************");
short[] arr1 = new short[4];
for (int i = 0; i < arr1.length; i++) {
System.out.println(arr1[i]);
}
System.out.println("************************");
float[] arr2 = new float[4];
for (int i = 0; i < arr2.length; i++) {
System.out.println(arr2[i]);
}
System.out.println("************************");
char[] arr3 = new char[4];
for (int i = 0; i < arr3.length; i++) {
System.out.println("----" + arr3[i] + "****");
}
if (arr3[0] == 0) {
System.out.println("你好");
}
System.out.println("************************");
boolean[] arr4 = new boolean[4];
for (int i = 0; i < arr4.length; i++) {
System.out.println(arr4[i]);
}
System.out.println("************************");
String[] arr5 = new String[5];
System.out.println(arr5[0]);
if (arr5[0] == null) {
System.out.println("北京天氣不錯");
}
}
} 2.1、記憶體的簡化結構
2.2、一維數組的記憶體解析
案例一
案例二
案例三
int[] arr = new int[]{1, 2, 3};
String[] arr1 = new String[4];
arr1[1] = "劉德華";
arr1[2] = "張學友";
arr1 = new String[3];
System.out.println(arr1[1]); // null 按照圖中步驟，最後數組記憶體解析完成，數組内部值為null。
2.3、練習
練習1
/*
* 升景坊單間短期出租4個月，550元/月（水電煤公攤，網費35元/月），空調、衛生間、廚房齊全。
* 屋内均是IT行業人士，喜歡安靜。是以要求來租者最好是同行或者剛畢業的年輕人，愛幹淨、安靜。
* eclipse代碼一鍵格式規範化：Ctrl+Shift+F
*/
public class ArrayDemo {
public static void main(String[] args) {
int[] arr = new int[]{8, 2, 1, 0, 3};
int[] index = new int[]{2, 0, 3, 2, 4, 0, 1, 3, 2, 3, 3};
String tel = "";
for (int i = 0; i < index.length; i++) {
tel += arr[index[i]];
}
// 聯系方式：18013820100
System.out.println("聯系方式：" + tel);
}
} 練習2
/*
* 2. 從鍵盤讀入學生成績，找出最高分，并輸出學生成績等級。
成績>=最高分-10 等級為’A’
成績>=最高分-20 等級為’B’
成績>=最高分-30 等級為’C’
其餘 等級為’D’
提示：先讀入學生人數，根據人數建立int數組，存放學生成績。
*/
public class ArrayDemo1 {
public static void main(String[] args) {
//1.使用Scanner，讀取學生個數
Scanner scanner = new Scanner(System.in);
System.out.println("請輸入學生人數：");
int number = scanner.nextInt();
//2.建立數組，存儲學生成績：動态初始化
int[] scores = new int[number];
//3.給數組中的元素指派
System.out.println("請輸入" + number + "個學生成績");
for (int i = 0; i < scores.length; i++) {
scores[i] = scanner.nextInt();
}
//4.擷取數組中的元素的最大值：最高分
int maxScore = 0;
for (int i = 0; i < scores.length; i++) {
if (maxScore < scores[i]) {
maxScore = scores[i];
}
}
//5.根據每個學生成績與最高分的內插補點，得到每個學生的等級，并輸出等級和成績
char level; //成績等級
for (int i = 0; i < scores.length; i++) {
if (maxScore - scores[i] <= 10) {
level = 'A';
} else if (maxScore - scores[i] <= 20) {
level = 'B';
} else if (maxScore - scores[i] <= 30) {
level = 'C';
} else {
level = 'D';
}
System.out.println("student " + i + " score is " + scores[i] + ",grade is " + level);
}
}
} 3、多元數組的使用
- Java 語言裡提供了支援多元數組的文法。
- 如果說可以把一維數組當成幾何中的線性圖形，那麼二維數組就相當于是一個表格，像下圖Excel中的表格一樣。
3.1、二位數組
代碼案例——ArrayTest2.java
/*
* 二維數組的使用
*
* 1.了解
* 對于二維數組的了解，我們可以看成是一維數組array1又作為另一個一維數組array2的元素而存在。
* 其實，從數組底層的運作機制來看，并沒有多元數組。
*
* 2.二維數組的使用：
* ① 二維數組的聲明和初始化
* ② 如何調用二維數組的指定位置的元素
* ③ 如何擷取二維數組的長度
* ④ 如何周遊二維數組
* ⑤ 二維數組元素的預設初始化值：見ArrayTest3.java
* ⑥ 二維數組的記憶體解析：見ArrayTest3.java
*
*/
public class ArrayTest2 {
public static void main(String[] args) {
//1.二維數組的聲明和初始化
int[] arr = new int[]{1, 2, 3}; //一維數組
//靜态初始化
int[][] arr1 = new int[][]{{1, 2, 3}, {4, 5}, {6, 7, 8}};
//動态初始化1
String[][] arr2 = new String[3][2];
//動态初始化2
String[][] arr3 = new String[3][];
//錯誤的情況
// String[][] arr4 = new String[][4];
// String[4][3] arr3 = new String[][];
// int[][] arr6 = new int[4][3]{ {1,2,3},{4,5},{6,7,8} };
//也是正确的寫法：
int[] arr4[] = new int[][]{{1, 2, 3}, {4, 5, 9, 10}, {6, 7, 8}};
int[] arr5[] = {{1, 2, 3}, {4, 5}, {6, 7, 8}};
int arr6[][] = new int[][]{{1, 2, 3}, {4, 5, 12, 6}, {7, 8, 9}};
int[] arr7[] = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int[][] arr8 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//2.如何調用二維數組的指定位置的元素
System.out.println(arr1[0][1]); //2
System.out.println(arr2[1][1]); //null
arr3[1] = new String[4]; //定義arr3的[1]為長度4的字元數組
System.out.println(arr3[1][0]); // null
//3.擷取二維數組的長度
System.out.println(arr3[1].length); //4
System.out.println(arr4.length); //3
System.out.println(arr4[0].length); //3
System.out.println(arr4[1].length); //4
//4.如何周遊二維數組
for (int i = 0; i < arr4.length; i++) {
for (int j = 0; j < arr4[i].length; j++) {
System.out.print(arr4[i][j] + " ");
}
System.out.println();
}
}
} 代碼案例——ArrayTest3.java
/*
* 二維數組的使用：
* 規定：二維數組分為外層數組的元素，内層數組的元素
* int[][] arr = new int[4][3];
* 外層元素：arr[0],arr[1]等
* 内層元素：arr[0][0],arr[1][2]等
*
* 5.二維數組元素的預設初始化值
* 針對于初始化方式一：比如：int[][] arr = new int[4][3];
* 外層元素的初始化值為：位址值
* 内層元素的初始化值為：與一維數組初始化情況相同
* 針對于初始化方式二：比如：int[][] arr = new int[4][];
* 外層元素的初始化值為：null
* 内層元素的初始化值為：不能調用，否則報錯
*
* 6.二維數組的記憶體解析
*
*/
public class ArrayTest3 {
public static void main(String[] args) {
int[][] arr = new int[4][3];
System.out.println(arr[0]); //位址值
System.out.println(arr[0][0]); //0
System.out.println(arr); //位址值
System.out.println("----------------------");
float[][] arr1 = new float[4][3];
System.out.println(arr1[0]); //位址值
System.out.println(arr1[0][0]); //0.0
System.out.println("----------------------");
String[][] arr2 = new String[4][2];
System.out.println(arr2[1]); //位址值
System.out.println(arr2[1][1]); //null
System.out.println("----------------------");
double[][] arr3 = new double[4][];
System.out.println(arr3[1]); //null
System.out.println(arr3[1][0]); //java.lang.NullPointerException
}
} 3.2、二維數組的記憶體解析
案例1
int[][] arr1 = new int[4][];
arr1[1] = new int[]{1,2,3};
arr1[2] = new int[4];
arr1[2][1] = 30; 案例2
int[][] arr4 = new int[3][];
System.out.println(arr4[0]); //null
System.out.println(arr4[0][0]); //報錯
arr4[0] = new int[3];
arr4[0][1] = 5;
arr4[1] = new int[]{1, 2}; 案例3
int[][] arr = new int[3][];
arr[1] = new int[]{1, 2, 3};
arr[2] = new int[3];
System.out.println(arr[0]); //null
System.out.println(arr[0][0]); //報異常 案例4
int[][] arr1 = new int[4][];
arr1[0] = new int[3];
arr1[1] = new int[]{1, 2, 3};
arr1[0][2] = 5;
arr1 = new int[2][]; 3.3、練習
練習1
public class ArrayExer1 {
public static void main(String[] args) {
int[][] arr = new int[][]{{3, 5, 8}, {12, 9}, {7, 0, 6, 4}};
int sum = 0; //記錄總和
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
sum += arr[i][j];
}
}
System.out.println("總和是:" + sum);
}
} 練習 2
練習 3
- 使用二維數組列印一個 10 行楊輝三角。
/*
* 使用二維數組列印一個10行的楊輝三角
*
* [提示]
* 1. 第一行有 1 個元素, 第 n 行有 n 個元素
* 2. 每一行的第一個元素和最後一個元素都是 1
* 3. 從第三行開始, 對于非第一個元素和最後一個元素的元素。即：
* yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
*/
public class YangHuiTest {
public static void main(String[] args) {
//1.聲明并初始化二維數組
int[][] yanghui = new int[10][];
//2.給數組的元素指派
for (int i = 0; i < yanghui.length; i++) {
yanghui[i] = new int[i + 1];
//2.1 給首末元素指派
yanghui[i][0] = 1; //首元素
yanghui[i][i] = 1; //末元素
//2.2 給每行的非首末元素指派
if (i > 1) { //從第三行開始
for (int j = 1; j < yanghui[i].length - 1; j++) {
yanghui[i][j] = yanghui[i - 1][j - 1] + yanghui[i - 1][j];
}
}
}
//3.周遊二維數組
for (int i = 0; i < yanghui.length; i++) {
for (int j = 0; j < yanghui[i].length; j++) {
System.out.print(yanghui[i][j] + " ");
}
System.out.println();
}
}
} 3.4、面試題
建立一個長度為 6 的 int 型數組，要求取值為 1-30，同時元素值各不相同
//此題隻做了解，初學不必精通。
public class ArrayEver4 {
public static void main(String[] args) {
// 方式一：
// 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]);
// }
// 方式二：
int[] arr2 = new int[6];
for (int i = 0; i < arr2.length; i++) {// [0,1) [0,30) [1,31)
arr2[i] = (int) (Math.random() * 30) + 1;
for (int j = 0; j < i; j++) {
if (arr2[i] == arr2[j]) {
i--;
break;
}
}
}
for (int i = 0; i < arr2.length; i++) {
System.out.println(arr2[i]);
}
}
} 4、數組中涉及到的常見算法
- 數組元素的指派(楊輝三角、回形數等)
- 求數值型數組中元素的最大值、最小值、平均數、總和等
- 數組的複制、反轉、查找(線性查找、二分法查找)
- 數組元素的排序算法
4.1、數組元素的指派
/*
* 此題了解！！！
*
* 回形數格式方陣的實作
* 從鍵盤輸入一個整數（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
*/
public class ArrayTest {
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();
}
}
} 4.2、數組元素的基本操作
/*
* 算法的考察：求數值型數組中元素的最大值、最小值、平均數、總和等
*
* 定義一個int型的一維數組，包含10個元素，分别賦一些随機整數，
* 然後求出所有元素的最大值，最小值，和值，平均值，并輸出出來。
* 要求：所有随機數都是兩位數。
*
* [10,99]
* 公式：擷取[a,b]範圍内的随機數：(int)( Math.random()*(b - a + 1) + a )
* (int)(Math.random() * (99 - 10 + 1) + 10)
*
*/
public class ArrayTest1 {
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) { //[10,99]
arr[i] = (int) (Math.random() * (99 - 10 + 1) + 10);
}
//周遊
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
System.out.println();
//求數組的最大值
int maxValue = arr[0]; //如果随機數是負數，就不能用0，用數組裡面的第一個元素
for (int i = 1; i < arr.length; i++) { //然後數組從第二個元素開始對比
if (maxValue < arr[i]) {
maxValue = arr[i];
}
}
System.out.println("最大值為:" + maxValue);
//求數組的最小值
int minValue = arr[0]; //如果随機數是負數，就不能用0，用數組裡面的第一個元素
for (int i = 1; i < arr.length; i++) { //然後數組從第二個元素開始對比
if (minValue > arr[i]) {
minValue = arr[i];
}
}
System.out.println("最小值為:" + minValue);
//求數組元素的總和
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
System.out.println("總和為:" + sum);
//求數組元素的平均數
int avgValue = sum / arr.length;
System.out.println("平均數為:" + avgValue);
}
} 4.3、數組元素的基本操作 2
/*
* 使用簡單數組
* (1)建立一個名為 ArrayTest2 的類，在 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。
*/
public class ArrayTest2 {
public static void main(String[] args) {
//聲明 array1 和 array2 兩個 int[]變量
int[] array1, array2;
//array1 初始化
array1 = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
//顯示 array1 的内容==周遊。
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + "\t");
}
//指派 array2 變量等于 array1
//不能稱作數組的複制。
array2 = array1;
//修改 array2 中的偶索引元素，使其等于索引值(如 array[0]=0,array[2]=2)。
for (int i = 0; i < array2.length; i++) {
if (i % 2 == 0) {
array2[i] = i;
}
}
System.out.println();
//列印出 array1。
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + "\t");
}
}
} 思考：上述 array1 和 array2 是什麼關系？
//array1 和 array2 位址值相同，都指向了堆空間的唯一的一個數組實體。
int[] array1, array2;
array1 = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
array2 = array1;
for (int i = 0; i < array2.length; i++) {
if (i % 2 == 0) {
array2[i] = i;
}
} 拓展：修改題目，實作 array2 對 array1 數組的複制
/*
* 拓展：修改題目，實作array2對array1數組的複制
*/
public class ArrayExer3 {
public static void main(String[] args) {
int[] array1, array2;
array1 = new int[]{2, 3, 5, 7, 11, 13, 17, 19};
//顯示array1的内容
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + "\t");
}
//修改題目，實作array2對array1數組的複制
//數組的複制
array2 = new int[array1.length];
for (int i = 0; i < array2.length; i++) {
array2[i] = array1[i];
}
//修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)
for (int i = 0; i < array2.length; i++) {
if (i % 2 == 0) {
array2[i] = i;
}
}
//列印出array1
System.out.println();
for (int i = 0; i < array1.length; i++) {
System.out.print(array1[i] + "\t");
}
}
} 4.4、數組的複制、反轉、查找 (線性查找、二分法查找)
/*
* 算法的考察：數組的複制、反轉、查找(線性查找、二分法查找)
*/
public class ArrayTest3 {
public static void main(String[] args) {
String[] arr = new String[]{"JJ", "DD", "MM", "BB", "GG", "AA"};
//數組的複制(差別于數組變量的指派:arr1 = arr)
String[] arr1 = new String[arr.length];
for (int i = 0; i < arr1.length; i++) {
arr1[i] = arr[i];
}
//數組的反轉
//方式一:
// for(int i = 0;i < arr1.length / 2;i++) {
// String temp = arr[i];
// arr[i] = arr[arr.length - i - 1];
// arr[arr.length - i - 1] = temp;
// }
//方式二:
// for(int i = 0,j = arr.length - 1;i < j;i++,j--) {
// String temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
//周遊
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "\t");
}
System.out.println();
//查找（或搜尋）
//線性查找：
String dest = "CC";
boolean isFlag = true;
for (int i = 0; i < arr.length; i++) {
if (dest.equals(arr[i])) {
System.out.println("找到了指定的元素，位置為：" + i);
isFlag = false;
break;
}
}
if (isFlag) {
System.out.println("很遺憾，沒有找到哦!");
}
//二分法查找：
//前提：所要查找的數組必須有序。
int[] arr2 = new int[]{-98, -34, 2, 34, 54, 66, 79, 105, 210, 333};
int dest1 = 54;
int head = 0; //初始的首索引
int end = arr2.length - 1; //初始的末索引
boolean isFlag1 = true;
while (head <= end) {
int middle = (head + end) / 2;
if (dest1 == arr2[middle]) {
System.out.println("找到了指定的元素，位置為：" + middle);
isFlag1 = false;
break;
} else if (arr2[middle] > dest1) {
end = middle - 1;
} else { //arr2[middle] < dest1
head = middle + 1;
}
}
if (isFlag1) {
System.out.println("很遺憾，沒有找到哦!");
}
}
} 4.5、數組元素的排序算法
- 排序：假設含有 n 個記錄的序列為{R1，R2，…,Rn},其相應的關鍵字序列為{K1，K2，…,Kn}。将這些記錄重新排序為{Ri1,Ri2,…,Rin},使得相應的關鍵字值滿足條 Ki1<=Ki2<=…<=Kin,這樣的一種操作稱為排序。
- 通常來說，排序的目的是快速查找。
- 衡量排序算法的優劣：
- 時間複雜度：分析關鍵字的比較次數和記錄的移動次數
- 空間複雜度：分析排序算法中需要多少輔助記憶體
- 穩定性：若兩個記錄 A 和 B 的關鍵字值相等，但排序後 A、B 的先後次序保持不變，則稱這種排序算法是穩定的。
- 排序算法分類：内部排序和外部排序。
- 内部排序：整個排序過程不需要借助于外部存儲器（如磁盤等），所有排序操作都在記憶體中完成。
- 外部排序：參與排序的資料非常多，資料量非常大，計算機無法把整個排序過程放在記憶體中完成，必須借助于外部存儲器（如磁盤）。外部排序最常見的是多路歸并排序。可以認為外部排序是由多次内部排序組成。
4.6、十大内部排序算法
- 選擇排序
- 直接選擇排序、堆排序
- 交換排序
- 冒泡排序、快速排序
- 插入排序
- 直接插入排序、折半插入排序、Shell 排序
- 歸并排序
- 桶式排序
- 基數排序
詳細操作，見《附錄》
附錄：尚矽谷_宋紅康_排序算法.pdf
4.7、算法的 5 大特征
| 輸入（Input） | 有 0 個或多個輸入資料，這些輸入必須有清楚的描述和定義 |
| 輸出（Output） | 至少有 1 個或多個輸出結果，不可以沒有輸出結果 |
| 有窮性（有限性，Finiteness） | 算法在有限的步驟之後會自動結束而不會無限循環，并且每一個步驟可以在可接受的時間内完成 |
| 确定性（明确性，Definiteness） | 算法中的每一步都有确定的含義，不會出現二義性 |
| 可行性（有效性，Effectiveness） | 算法的每一步都是清楚且可行的，能讓使用者用紙筆計算而求出答案 |
說明：滿足确定性的算法也稱為：确定性算法。現在人們也關注更廣泛的概念，例如考慮各種非确定性的算法，如并行算法、機率算法等。另外，人們也關注并不要求終止的計算描述，這種描述有時被稱為過程（procedure）。
4.8、冒泡排序(重要)
- 冒泡排序的基本思想：通過對待排序序列從前向後，依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼較大的元素逐漸從前部移向後部。
- 因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序， 是以要在排序過程中設定一個标志swap判斷元素是否進行過交換。進而減少不必要的比較。
/*
* 數組的冒泡排序的實作
*/
public class BubbleSortTest {
public static void main(String[] args) {
int[] arr = new int[]{43, 32, 76, -98, 0, 64, 33, -21, 32, 99};
//冒泡排序
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (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] + " ");
}
}
} 4.9、快速排序(初學Java，僅作了解)
快速排序（Quick Sort）由圖靈獎獲得者Tony Hoare發明，被列為20世紀十大算法之一，是迄今為止所有内排序算法中速度最快的一種。冒泡排序的更新版，交換排序的一種。快速排序的時間複雜度為O(nlog(n))。
排序思想：
- 從數列中挑出一個元素，稱為"基準"（pivot），
- 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區結束之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
- 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
- 遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的疊代（iteration）中，它至少會把一個元素擺到它最後的位置去。
/**
* 快速排序
* 通過一趟排序将待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分關鍵字小，
* 則分别對這兩部分繼續進行排序，直到整個序列有序。
*/
public class QuickSort {
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(int[] data, int start, int end) {
if (start < end) {
int base = data[start];
int low = start;
int high = end + 1;
while (true) {
while (low < end && data[++low] - base <= 0) ;
while (high > start && data[--high] - base >= 0) ;
if (low < high) {
swap(data, low, high);
} else {
break;
}
}
swap(data, start, high);
subSort(data, start, high - 1);//遞歸調用
subSort(data, high + 1, end);
}
}
public static void quickSort(int[] data) {
subSort(data, 0, data.length - 1);
}
public static void main(String[] args) {
int[] data = {9, -16, 30, 23, -30, -49, 25, 21, 30};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之後：\n" + java.util.Arrays.toString(data));
}
} 4.10、排序算法性能對比
各種内部排序方法性能比較
- 從平均時間而言：快速排序最佳。但在最壞情況下時間性能不如堆排序和歸并排序。
- 從算法簡單性看：由于直接選擇排序、直接插入排序和冒泡排序的算法比較簡單，将其認為是簡單算法。對于Shell排序、堆排序、快速排序和歸并排序算法，其算法比較複雜，認為是複雜排序。
- 從穩定性看：直接插入排序、冒泡排序和歸并排序是穩定的；而直接選擇排序、快速排序、Shell排序和堆排序是不穩定排序
- 從待排序的記錄數n的大小看，n較小時，宜采用簡單排序；而n較大時宜采用改進排序。
排序算法的選擇
- 若n較小(如n≤50)，可采用直接插入或直接選擇排序。當記錄規模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數少于直接插入，應選直接選擇排序為宜。
- 若檔案初始狀态基本有序(指正序)，則應選用直接插入、冒泡或随機的快速排序為宜；
- 若n較大，則應采用時間複雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。
5、Arrays 工具類的使用
java.util.Arrays類即為操作數組的工具類，包含了用來操作數組（比如排序和搜尋）的各種方法。
| 1 | boolean equals(int[] a,int[] b) | 判斷兩個數組是否相等。 |
| 2 | String toString(int[] a) | 輸出數組資訊。 |
| 3 | void fill(int[] a,int val) | 将指定值填充到數組之中。 |
| 4 | void sort(int[] a) | 對數組進行排序。 |
| 5 |
/*
* java.util.Arrays:操作數組的工具類，裡面定義了很多操作數組的方法
*/
public class ArrayTest4 {
public static void main(String[] args) {
//1.boolean equals(int[] a,int[] b) 判斷兩個數組是否相等
int[] arr1 = new int[]{1, 2, 3, 4};
int[] arr2 = new int[]{1, 3, 2, 4};
boolean isEquals = Arrays.equals(arr1, arr2);
System.out.println(isEquals); //false,數組是有序的
//2.String toString(int[] a) 輸出數組資訊
System.out.println(Arrays.toString(arr1));
//3.void fill(int[] a,int val) 将指定值替換到數組的所有元素中
Arrays.fill(arr1, 10);
System.out.println(Arrays.toString(arr1));
//4.void sort(int[] a) 對數組進行排序
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
//5.int binarySearch(int[] a,int key)
int[] arr3 = new int[]{-98, -34, 2, 34, 54, 66, 79, 105, 210, 333};
int index = Arrays.binarySearch(arr3, 210);
if (index >= 0) {
System.out.println(index);
} else {
System.out.println("未找到");
}
}
} 6、數組使用中的常見異常
/*
* 數組中的常見異常：
* 1.數組角标越界的異常:ArrayIndexOutOfBoundsException
*
* 2.空指針異常:NullPointerException
*/
public class ArrayExceptionTest {
public static void main(String[] args) {
//1.數組角标越界的異常:ArrayIndexOutOfBoundsException
int[] arr = new int[]{1, 2, 3, 4, 5};
// for(int i = 0;i <= arr.length;i++) {
// System.out.println(arr[i]);
// }
// System.out.println(arr[-2]);
//2.空指針異常:NullPointerException
//情況一:
// int[] arr1 = new int[] {1,2,3};
// arr1 = null;
// System.out.println(arr1[0]);
//情況二:
// int[][] arr2 = new int[4][];
// System.out.println(arr2[0][0]);
//情況三:
// String[] arr3 = new String[] {"AA","BB","CC"};
// arr3[0] = null;
// System.out.println(arr3[0].toString());
}
}