java初級(jí)編程
多維數(shù)組的使用
練習(xí)1
練習(xí)1
/*
* 或許arr數(shù)組中所有元素的和
* 使用for的嵌套循環(huán)
*/
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);
}
}
練習(xí)2
==int[] x,y[]==
- x定義為一維數(shù)組谴分；y是二維數(shù)組庵佣；int[]x;int[]y[]
+ 一維數(shù)組賦值：int[] x 或者int x[]
+ 二維數(shù)組賦值：int[][]y 或 者 int[] y[] 或者 int y[][]
//以下是否能通過(guò)編譯
+ x[0] = y; no
+ y[0] = x; yes
+ y[0][0] = x; no
+ x[0][0] = y; no
+ y[0][0] = x[0]; yes
+ x = y; no
練習(xí)3
- 使用二維數(shù)組打印一個(gè)10行楊輝三角
- 第一行有1個(gè)元素，第n行有n個(gè)元素
- 每一行的第一個(gè)元素和最后一個(gè)元素都是1
- 從第三行開(kāi)始谴蔑，對(duì)于非第一個(gè)元素和最后一個(gè)元素的元素。即：
yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
/*
* 使用二維數(shù)組打印一個(gè) 10 行楊輝三角。
【提示】
1. 第一行有 1 個(gè)元素, 第 n 行有 n 個(gè)元素
2. 每一行的第一個(gè)元素和最后一個(gè)元素都是 1
3. 從第三行開(kāi)始, 對(duì)于非第一個(gè)元素和最后一個(gè)元素的元素陕凹。即：
yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
*
*/
public class YangHuiTest {
public static void main(String[] args) {
//1.聲明并初始化二維數(shù)組
int[][] yangHui = new int[10][];
//2.給數(shù)組的元素賦值
for(int i = 0;i < yangHui.length;i++){
yangHui[i] = new int[i + 1];
//2.1 給首末元素賦值
yangHui[i][0] = 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.遍歷二維數(shù)組
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();
}
}
}
數(shù)組中涉及到的常見(jiàn)的算法題
- 數(shù)組元素的賦值（楊輝三角、回形數(shù)等）
- 求數(shù)值型數(shù)組中元素的最大值鳄炉、最小值杜耙、平均數(shù)、總和等
- 數(shù)組的復(fù)制拂盯、反轉(zhuǎn)佑女、查找（線性查找、二分法）
- 數(shù)組元素的排序算法
練習(xí)一
創(chuàng)建一個(gè)長(zhǎng)度為6的int型數(shù)組谈竿，要求數(shù)組元素的值都在1-30之間团驱，且是隨機(jī)賦值。同時(shí)空凸，要求元素的值各不相同嚎花。
public class ArrayExer3 {
public static void main(String[] args){
int[] arr = new int[6];
for (int i = 0; i < arr.length; i++){
// 公式：Math.random()*(n-m)+m，生成大于等于m小于n的隨機(jī)數(shù)呀洲；
arr[i] = (int)(Math.random()*30 + 1);
boolean judgement = true;
while(true){
for (int j = 0;j < i;j++){
if (arr[j] == arr[i]){
judgement = true;
break;
}
}
if (judgement){
arr[i] = (int)(Math.random()*30 + 1);
judgement = false;
continue;
}
break;
}
}
for (int i = 0; i < arr.length; i++){
System.out.println(arr[i]);
}
}
}
//厲害方法
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]);
}
}
}
練習(xí)二
/*
* 回形數(shù)格式方陣的實(shí)現(xiàn)
從鍵盤(pán)輸入一個(gè)整數(shù)（1~20）
則以該數(shù)字為矩陣的大小紊选，把1,2,3…n*n 的數(shù)字按照順時(shí)針螺旋的形式填入其中啼止。例如： 輸入數(shù)字2，則程序輸出： 1 2
4 3
輸入數(shù)字3兵罢，則程序輸出： 1 2 3
8 9 4
7 6 5
輸入數(shù)字4献烦， 則程序輸出：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
*/
import java.util.Scanner;
public class ArrayExer4 {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int len = scanner.nextInt();
int[][] arr = new int[len][len];
int s = len * len;
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();
}
}
}
練習(xí)三
/*
* 算法的考查：求數(shù)值型數(shù)組中元素的最大值、最小值卖词、平均數(shù)巩那、總和等
*
* 定義一個(gè)int型的一維數(shù)組，包含10個(gè)元素此蜈，分別賦一些隨機(jī)整數(shù)即横，
* 然后求出所有元素的最大值，最小值裆赵，和值东囚，平均值，并輸出出來(lái)顾瞪。
* 要求：所有隨機(jī)數(shù)都是兩位數(shù)舔庶。
*
* [10,99]
* 公式：(int)(Math.random() * (99 - 10 + 1) + 10)
* random得到double型
*/
public class ArrayTest1 {
public static void main(String[] args){
int[] arr = new int[10];
for(int i = 0;i < arr.length;i++){
arr[i] = (int)(Math.random() * (99 - 10 + 1) + 10);
}
//遍歷
for(int i = 0;i <arr.length;i++){
System.out.println(arr[i]);
}
System.out.println();
//求數(shù)組最大值
//int max = 0;
int max = arr[0];
for(int i = 0;i <arr.length;i++){
if(max < arr[i]){
max = arr[i];
}
}
System.out.println(max);
//求數(shù)組最小值
int min =arr[0];
for(int i = 0;i <arr.length;i++){
if(min > arr[i]){
min = arr[i];
}
}
System.out.println(min);
//求數(shù)組總和
int sum = 0;
for(int i = 0;i <arr.length;i++){
sum += arr[i];
}
System.out.println(sum);
//求數(shù)組平均數(shù)
int avg = sum / arr.length;
System.out.println(avg);
}
}
練習(xí)四
/*
* 使用簡(jiǎn)單數(shù)組
(1)創(chuàng)建一個(gè)名為ArrayExer5的類，在main()方法中聲明array1和array2兩個(gè)變量陈醒，他們是int[]類型的數(shù)組惕橙。
(2)使用大括號(hào){}，把a(bǔ)rray1初始化為8個(gè)素?cái)?shù)：2,3,5,7,11,13,17,19钉跷。
(3)顯示array1的內(nèi)容弥鹦。
(4)賦值array2變量等于array1，修改array2中的偶索引元素爷辙，使其等于索引值(如array[0]=0,array[2]=2)彬坏。打印出array1。
*
* 思考：array1和array2是什么關(guān)系膝晾？array1和array2地址值相同栓始，都指向了堆空間的唯一的一個(gè)數(shù)組實(shí)體。
* 拓展：修改題目血当，實(shí)現(xiàn)array2對(duì)array1數(shù)組的復(fù)制
*/
public class ArrayExer5 {
public static void main(String[] args){
int[] array1,array2;
array1 = new int[]{2,3,5,7,11,13,17,19};
//顯示array1內(nèi)容
for (int i = 0;i < array1.length;i++){
System.out.print(array1[i] + "\t");
}
//賦值array2變量等于array1
array2 = array1;//僅僅將array1的地址給了array2幻赚，但實(shí)際上只有一個(gè)數(shù)組，僅僅是地址值一樣
//只有通過(guò)new才會(huì)產(chǎn)生新的數(shù)組臊旭，這里只有一個(gè)new
//此處不能稱作數(shù)組的復(fù)制
//修改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");
}
}
}
地址值的變化并非復(fù)制
==復(fù)制文件與復(fù)制快捷方式的區(qū)別==
//數(shù)組的復(fù)制
public class ArrayExer6 {
public static void main(String[] args){
int[] array1,array2;
array1 = new int[]{2,3,5,7,11,13,17,19};
//顯示array1內(nèi)容
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];
}
數(shù)組的復(fù)制操作
練習(xí)五
/*
* 算法的考查：數(shù)組的復(fù)制、反轉(zhuǎn)离熏、查找(線性查找佳谦、二分法查找)
*
*
*/
public class ArrayTest2 {
public static void main(String[] args) {
String[] arr = new String[]{"JJ","DD","MM","BB","GG","AA"};
//數(shù)組的復(fù)制(區(qū)別于數(shù)組變量的賦值：arr1 = arr)
String[] arr1 = new String[arr.length];
for(int i = 0;i < arr1.length;i++){
arr1[i] = arr[i];
}
//數(shù)組的反轉(zhuǎn)
//法一：注意下標(biāo)和長(zhǎng)度的區(qū)別
for(int i = 0;i < 0.5 * arr.length;i++){
String transition = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = transition;
}
//法二：
// for(int i = 0,j = arr.length - 1;i < j;i++,j--){
// String transition = arr[i];
// arr[i] = arr[j];
// arr[j] = transition;
// }
for (int i = 0;i < arr.length;i++){
System.out.print(arr[i] + "\t");
}
System.out.println();
//查找
//線性查找
String dest = "BB";
//equals.:比較字符串內(nèi)的內(nèi)容是否相同
boolean isFlag = true;//標(biāo)識(shí)判斷
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("很遺憾，未找到");
}
//二分法查找：相對(duì)于線性查找滋戳，更快速
//前提：所要查找的數(shù)組必須有序
int[] arr2 = new int[]{-98,-40,-34,-5,3,4,25,34,90};
int dest1 = -34;
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{
head = middle + 1;
}
}
if(isFlag1){
System.out.println("很遺憾啥刻，未找到");
}
}
}
二分法
排序算法
排序：假設(shè)含有n個(gè)記錄的序列為{R1,R2,...Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,...Kn}矢棚。將這些記錄重新排序?yàn)閧Ri1,Ri2,...<Rin}郑什，使得相應(yīng)的關(guān)鍵字值滿足條件Ki1<=Ki2<=Ki3<=...<=Kin,這樣的一種操作稱為排序府喳。
通常來(lái)說(shuō)蒲肋，排序的目的是為了快速查找
-
衡量排序算法的優(yōu)劣：
- 時(shí)間復(fù)雜度：分析關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)
- 空間復(fù)雜度：分析排序算法中需要多少輔助內(nèi)存
- 穩(wěn)定性：若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A钝满、B的先后次序保持不變兜粘，則稱這種算法是穩(wěn)定的。
-
排序算法分類：內(nèi)部排序和外部排序
- 內(nèi)部排序：整個(gè)排序過(guò)程中不需要借助于外部存儲(chǔ)器(如磁盤(pán)等)弯蚜，所有排序操作都在內(nèi)存中完成孔轴。
- 外部排序：參與排序的數(shù)據(jù)非常多，數(shù)據(jù)量非常大碎捺，計(jì)算機(jī)無(wú)法把整個(gè)排序過(guò)程放在內(nèi)存中完成路鹰，必須借助于外部存儲(chǔ)器(如磁盤(pán))。外部排序最常見(jiàn)的是多路歸并排序收厨〗可以認(rèn)為外部排序是由多次內(nèi)部排序組成。
-
十大內(nèi)部排序算法
- 選擇排序
- 直接選擇排序
- *堆排序 *
- 交換排序
- ==冒泡排序==
- ==快速排序==
- 插入排序
- 直接插入排序
- 折半插入排序
- Shell排序(希爾排序)
- 歸并排序
- 桶式排序
- 基數(shù)排序
- 選擇排序
-
算法的5大特征
- 輸入(input):有0個(gè)或多個(gè)輸入數(shù)據(jù)诵叁，這些輸入數(shù)據(jù)必須有清楚的描述和定義
- 輸出(Output):至少有1個(gè)或多個(gè)輸出結(jié)果雁竞，不可以沒(méi)有輸出結(jié)果
- 有窮性(有限性，F(xiàn)initeness):算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無(wú)線循環(huán)拧额，并且每一個(gè)步驟可以在可接受的時(shí)間內(nèi)完成
- 確定性(明確性碑诉，Definiteness):算法的每一步都有確定的含義，不會(huì)出現(xiàn)二義性
- 可行性(有效性侥锦，Effectiveness):算法的每一步都是清楚且可行的进栽，能讓用戶用紙筆計(jì)算求出答案
==人們也關(guān)注并不要求終止的計(jì)算描述，這種描述有時(shí)被稱為過(guò)程(procedure)==
冒泡排序
- 比較相鄰的元素恭垦。如果第一個(gè)二大（升序）快毛，就交換他們兩
- 對(duì)每一相鄰元素作同樣的工作，從開(kāi)始第到結(jié)尾最后署照。這步做完后祸泪，最后的元素會(huì)是大數(shù)。
- 針對(duì)所有的元素重復(fù)以上步驟建芙，除了最后一個(gè)没隘。
- 持續(xù)每次對(duì)越來(lái)少的元素重復(fù)上面步驟，直到?jīng)]有任何一數(shù)字需要比較為止禁荸。
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 - 1;i++){
System.out.print(arr[i] + "\t");
}
}
}
快速排序
- 快速排序通常明顯比O(nlogn)的其他算法更快右蒲，因此常被采用阀湿，快速排序算法采用了分治法的思想
排序思想
- 從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"(pivot)
- 重新排序數(shù)列瑰妄，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面陷嘴，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)后面(相同的數(shù)可以到任一邊)。在這個(gè)分區(qū)結(jié)束之后间坐，該基準(zhǔn)就處于數(shù)列的中間位置灾挨。這個(gè)稱為分區(qū)(partition)操作
- 遞歸地(recursive)把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
- 遞歸的最底部情形，是數(shù)列的大小是零或一竹宋，也就是永遠(yuǎn)都已經(jīng)被排序好了劳澄。雖然一直遞歸下去，但是這個(gè)算法總會(huì)結(jié)束蜈七，因?yàn)樵诿看蔚牡?iteration)中秒拔，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去
快速排序過(guò)程
/**
* 快速排序
* 通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分關(guān)鍵字小飒硅，
* 則分別對(duì)這兩部分繼續(xù)進(jìn)行排序砂缩，直到整個(gè)序列有序。
*/
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);//遞歸調(diào)用
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));
}
}
排序算法的的性能對(duì)比
- 從平均時(shí)間而言 ：快速排序最佳三娩。 但在最壞情況下時(shí)間性能不如堆排序和歸并排序庵芭。
- 從算法簡(jiǎn)單性看 ：由于直接選擇排序、插入和冒泡的算法比較簡(jiǎn)單尽棕，將其認(rèn)為是簡(jiǎn)單算法喳挑。 對(duì)于Shell排序 、堆排序滔悉、快速排序和歸并排序算法伊诵，其算法比較復(fù)雜，認(rèn)為是復(fù)雜排序回官。
- 從穩(wěn)定性看：直接插入排序曹宴、冒泡排序和歸并排序時(shí)穩(wěn)定的；而直接選擇排序歉提、快速排序笛坦、shell排序和堆排序是不穩(wěn)定排序。
- 從待排序的記錄數(shù)n的大小看 苔巨，n較小時(shí)版扩，宜采用簡(jiǎn)單排序；而 n較大時(shí)宜采用改進(jìn)排序
排序算法的性能
Arrays工具類的使用
- java.util.Arrays類即為操作數(shù)組的工具類侄泽，包含用來(lái)操作數(shù)組(比如排序和搜索)的各種方法礁芦。
Arrays工具類常見(jiàn)方法
import java.util.Arrays;
/*
* java.util.Arrays:操作數(shù)組的工具類，里面定義了很多操作數(shù)組的方法
*
*
*/
public class ArraysTest {
public static void main(String[] args) {
//1.boolean equals(int[] a,int[] b):判斷兩個(gè)數(shù)組是否相等。數(shù)組要有順序
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);
//2.String toString(int[] a):輸出數(shù)組信息柿扣。
System.out.println(Arrays.toString(arr1));
//3.void fill(int[] a,int val):將指定值填充到數(shù)組之中肖方。
Arrays.fill(arr1,10);
System.out.println(Arrays.toString(arr1));
//4.void sort(int[] a):對(duì)數(shù)組進(jìn)行排序。
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("未找到");
}
}
}
數(shù)組使用中的常見(jiàn)異常
/*
* 數(shù)組中的常見(jiàn)異常：
* 1. 數(shù)組角標(biāo)越界的異常：ArrayIndexOutOfBoundsExcetion
*
* 2. 空指針異常：NullPointerException
*
*/
public class ArrayException {
public static void main(String[] args) {
//1. 數(shù)組角標(biāo)越界的異常：ArrayIndexOutOfBoundsExcetion,不在指定的范圍內(nèi)的情況
int[] arr = new int[]{1,2,3,4,5};
// for(int i = 0;i <= arr.length;i++){
// System.out.println(arr[i]);
// }此處出現(xiàn)了角標(biāo)5
// System.out.println(arr[-2]);
// System.out.println("hello");
//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());
}
}
數(shù)組重點(diǎn)
- 一維數(shù)組使用Ｎ醋础８┗！
- 二維數(shù)組使用Ｋ静荨＜璐埂！
