01 ASCII編碼表
數(shù)字0-9對應(yīng)ASCII編碼十進(jìn)制為48-57
字母a-z對應(yīng)ASCII編碼十進(jìn)制為97-122
字母A-Z對應(yīng)ASCII編碼十進(jìn)制為65-90
02 數(shù)組逆序
數(shù)組的逆序：數(shù)組中最遠(yuǎn)的兩個(gè)索引,進(jìn)行位置交換,實(shí)現(xiàn)數(shù)組的逆序
實(shí)現(xiàn)代碼：
public class ArrayMethodTest_1{
public static void main(String[] args){
int[] arr = {3,5,7,1,0,9,-2};
//調(diào)用數(shù)組的逆序方法
reverse(arr);
//看到數(shù)組的元素,遍歷
printArray(arr);
}
/*
定義方法,實(shí)現(xiàn)數(shù)組的逆序
返回值: 沒有返回值
參數(shù): 數(shù)組就是參數(shù)
*/
public static void reverse(int[] arr){
//利用循環(huán),實(shí)現(xiàn)數(shù)組遍歷,遍歷過程中,最遠(yuǎn)端換位
//for的第一項(xiàng),定義2個(gè)變量, 最后,兩個(gè)變量++ --
for( int min = 0 , max = arr.length-1 ; min < max ; min++,max--){
//對數(shù)組中的元素,進(jìn)行位置交換
//min索引和max索引的元素交換
//定義變量,保存min索引
int temp = arr[min];
//max索引上的元素,賦值給min索引
arr[min] = arr[max];
//臨時(shí)變量,保存的數(shù)據(jù),賦值到max索引上
arr[max] = temp;
}
}
}
03 選擇排序
a、選擇排序原理
- 通過觀察發(fā)現(xiàn)，本題目要實(shí)現(xiàn)把數(shù)組元素{13,46,22,65,3}進(jìn)行排序
- 提到數(shù)組排序，就要進(jìn)行元素值大小的比較，通過上圖發(fā)現(xiàn)，我們想完成排序要經(jīng)過若干次的比較才能夠完成。
- 上圖中用每圈要比較的第一個(gè)元素與該元素后面的數(shù)組元素依次比較到數(shù)組的最后一個(gè)元素，把小的值放在第一個(gè)數(shù)組元素中，數(shù)組循環(huán)一圈后，則把最小元素值互換到了第一個(gè)元素中。
- 數(shù)組再循環(huán)一圈后，把第二小的元素值互換到了第二個(gè)元素中。按照這種方式，數(shù)組循環(huán)多圈以后，就完成了數(shù)組元素的排序。這種排序方式我們稱為選擇排序。
b、 解題步驟
使用for循環(huán)（外層循環(huán)），指定數(shù)組要循環(huán)的圈數(shù)（通過圖解可知，數(shù)組循環(huán)的圈數(shù)為數(shù)組長度 - 1）
在每一圈中，通過for循環(huán)（內(nèi)層循環(huán)）完成數(shù)組要比較的第一個(gè)元素與該元素后面的數(shù)組元素依次比較到數(shù)組的最后一個(gè)元素，把小的值放在第一個(gè)數(shù)組元素中
在每一圈中，要參與比較的第一個(gè)元素由第幾圈循環(huán)來決定。如上圖所示
進(jìn)行第一圈元素比較時(shí)，要比較的第一個(gè)元素為數(shù)組第一個(gè)元素，即索引為0的元素
進(jìn)行第二圈元素比較時(shí)，要比較的第一個(gè)元素為數(shù)組第二個(gè)元素，即索引為1的元素
-
依次類推，得出結(jié)論：進(jìn)行第n圈元素比較時(shí)，要比較的第一個(gè)元素為數(shù)組第n個(gè)元素，即數(shù)組索引為n-1的元素
public class SelectSortTest{ public static void main(String[] args){ int[] arr = {3,1,4,2,56,7,0}; //調(diào)用選擇排序方法 //selectSort(arr); printArray(arr); } /* 定義方法,實(shí)現(xiàn)數(shù)組的選擇排序 返回值: 沒有 參數(shù): 數(shù)組 實(shí)現(xiàn)步驟: 1.嵌套循環(huán)實(shí)現(xiàn)排序 外循環(huán),控制的是一共比較了多少次 內(nèi)循環(huán),控制的是每次比較了多少個(gè)元素 2. 判斷元素的大小值 小值,存儲(chǔ)到小的索引 */ public static void selectSort(int[] arr){ for(int i = 0 ; i < arr.length - 1; i++){ //內(nèi)循環(huán),是每次都在減少,修改變量的定義 for(int j = i+1 ; j < arr.length ; j++){ //數(shù)組的元素進(jìn)行判斷 if(arr[i] > arr[j]){ //數(shù)組的換位 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } } /* 定義方法,實(shí)現(xiàn)功能 返回值: void 方法參數(shù): 數(shù)組 */ public static void printArray(int[] arr){ //輸出一半中括號(hào),不要換行打印 System.out.print("["); //數(shù)組進(jìn)行遍歷 for(int i = 0 ; i < arr.length ; i++){ //判斷遍歷到的元素,是不是數(shù)組的最后一個(gè)元素 //如何判斷 循環(huán)變量 到達(dá) length-1 if( i == arr.length-1 ){ //輸出數(shù)組的元素和] System.out.print(arr[i]+"]"); }else{ //不是數(shù)組的最后一個(gè)元素,輸出數(shù)組元素和逗號(hào) System.out.print(arr[i]+","); } } System.out.println(); } }
04 冒泡排序
a、原理
通過觀察發(fā)現(xiàn)，本題目要實(shí)現(xiàn)把數(shù)組元素{13,46,22,65,3}進(jìn)行排序
提到數(shù)組排序，就要進(jìn)行元素值大小的比較，通過上圖發(fā)現(xiàn)，我們想完成排序要經(jīng)過若干次的比較才能夠完成。
上圖中相鄰的元素值依次比較，把大的值放后面的元素中，數(shù)組循環(huán)一圈后，則把最大元素值互換到了最后一個(gè)元素中。
*數(shù)組再循環(huán)一圈后，把第二大的元素值互換到了倒數(shù)第二個(gè)元素中。按照這種方式，數(shù)組循環(huán)多圈以后，就完成了數(shù)組元素的排序。這種排序方式我們稱為冒泡排序。
b、 解題步驟使用for循環(huán)（外層循環(huán)），指定數(shù)組要循環(huán)的圈數(shù)（通過圖解可知，數(shù)組循環(huán)的圈數(shù)為數(shù)組長度 - 1）
在每一圈中，通過for循環(huán)（內(nèi)層循環(huán)）完成相鄰的元素值依次比較，把大的值放后面的元素中
每圈內(nèi)層循環(huán)的次數(shù)，由第幾圈循環(huán)來決定。如上圖所示
進(jìn)行第一圈元素比較時(shí)，內(nèi)層循環(huán)次數(shù)為數(shù)組長度 - 1
進(jìn)行第二圈元素比較時(shí)，內(nèi)層循環(huán)次數(shù)為數(shù)組長度 - 2
-
依次類推，得出結(jié)論：進(jìn)行第n圈元素比較時(shí)，內(nèi)層循環(huán)次數(shù)為數(shù)組長度 - n
public class BubbleSortTest{ public static void main(String[] args){ int[] arr = {3,1,4,2,56,7,0}; //調(diào)用選擇排序方法 //selectSort(arr); //調(diào)用冒泡排序方法 bubbleSort(arr); printArray(arr); } public static void bubbleSort(int[] arr){ for(int i = 0 ; i < arr.length - 1; i++){ //每次內(nèi)循環(huán)的比較,從0索引開始, 每次都在遞減 for(int j = 0 ; j < arr.length-i-1; j++){ //比較的索引,是j和j+1 if(arr[j] > arr[j+1]){ int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } /* 定義方法,實(shí)現(xiàn)功能 返回值: void 方法參數(shù): 數(shù)組 */ public static void printArray(int[] arr){ //輸出一半中括號(hào),不要換行打印 System.out.print("["); //數(shù)組進(jìn)行遍歷 for(int i = 0 ; i < arr.length ; i++){ //判斷遍歷到的元素,是不是數(shù)組的最后一個(gè)元素 //如何判斷 循環(huán)變量 到達(dá) length-1 if( i == arr.length-1 ){ //輸出數(shù)組的元素和] System.out.print(arr[i]+"]"); }else{ //不是數(shù)組的最后一個(gè)元素,輸出數(shù)組元素和逗號(hào) System.out.print(arr[i]+","); } } System.out.println(); } }
05 數(shù)組的折半查找
a、原理分析
- 通過觀察發(fā)現(xiàn)，本題目要實(shí)現(xiàn)查找指定數(shù)值在元素有序的數(shù)組中存儲(chǔ)的位置（索引），返回該位置（索引）。
- 最中間位置的元素值與要查找的指定數(shù)值進(jìn)行比較，若不相等，則根據(jù)比較的結(jié)果，縮小查詢范圍為上次數(shù)組查詢范圍的一半；
再根據(jù)新的查詢范圍，更新最中間元素位置，然后使用中間元素值與要查找的指定數(shù)值進(jìn)行比較
比較結(jié)果相等，返回中間元素值的索引
比較結(jié)果不相等，繼續(xù)縮小查詢范圍為上次數(shù)組查詢范圍的一半，更新最中間元素位置，繼續(xù)比較，依次類推。 - 當(dāng)查詢范圍縮小到小于0個(gè)元素時(shí)，則指定數(shù)值沒有查詢到，返回索引值-1。
b、解題步驟
定義3個(gè)用來記錄索引值的變量，變量min記錄當(dāng)前范圍最小索引值，初始值為0；變量max記錄當(dāng)前范圍最大索引值，初始值為數(shù)組長度-1；變量mid記錄當(dāng)前當(dāng)前范圍最中間元素的索引值，初始值為(min+max) / 2
使用循環(huán)，判斷當(dāng)前范圍下，最中間元素值與指定查找的數(shù)值是否相等
若相等，結(jié)束循環(huán)，返回當(dāng)前范圍最中間元素的索引值mid
若不相等，根據(jù)比較結(jié)果，縮小查詢范圍為上一次查詢范圍的一般
中間元素值 比 要查詢的數(shù)值大，說明要查詢的數(shù)值在當(dāng)前范圍的最小索引位置與中間索引位置之間，此時(shí)，更新查詢范圍為:
范圍最大索引值 = 上一次中間索引位置 -1；
中間元素值 比 要查詢的數(shù)值小，說明要查詢的數(shù)值在當(dāng)前范圍的最大索引位置與中間索引位置之間，此時(shí)，更新查詢范圍為:
范圍最小索引值 = 上一次中間索引位置 +1；
在新的查詢范圍中，更新中間元素值的位置，再次使用最中間元素值與指定查找的數(shù)值是否相等。
中間索引值 = (范圍最小索引值 +范圍最大索引值) / 2;-
每次查詢范圍縮小一半后，使用if語句判斷，查詢范圍是否小于0個(gè)元素，若小于0個(gè)元素，則說明指定數(shù)值沒有查詢到，返回索引值-1。
public class BinarySearchTest{ public static void main(String[] args){ int[] arr = {1,3,5,7,9,11,15}; int index = binarySearch(arr,10); System.out.println(index); } /* 定義方法,實(shí)現(xiàn),折半查找 返回值: 索引 參數(shù): 數(shù)組,被找的元素 實(shí)現(xiàn)步驟: 1. 需要的變量定義 三個(gè),三個(gè)指針 2. 進(jìn)行循環(huán)折半 可以折半的條件 min <= max 3. 讓被找元素,和中間索引元素進(jìn)行比較 元素 > 中間索引 小指針= 中間+1 元素 < 中間索引 大指針= 中間-1 元素 == 中間索引 找到了,結(jié)束了,返回中間索引 4. 循環(huán)結(jié)束,無法折半 元素沒有找到 ,返回-1 */ public static int binarySearch(int[] arr, int key){ //定義三個(gè)指針變量 int min = 0 ; int max = arr.length -1 ; int mid = 0; //循環(huán)折半,條件 min<=max while( min <= max){ //公式,計(jì)算中間索引 mid = (min+max)/2; //讓被找元素,和中間索引元素進(jìn)行比較 if(key > arr[mid]){ min = mid + 1; }else if (key < arr[mid]){ max = mid - 1; }else{ //找到元素,返回元素索引 return mid; } } return -1; } /* 定義方法,實(shí)現(xiàn)數(shù)組的普通查詢 返回值: 索引 參數(shù): 數(shù)組, 被找的元素 實(shí)現(xiàn)步驟: 1. 遍歷數(shù)組 2. 遍歷過程中,使用元素和數(shù)組中的元素進(jìn)行比較 如果相同,返回元素在數(shù)組中的索引 如果不同,返回負(fù)數(shù) */ public static int search(int[] arr, int key){ //遍歷數(shù)組 for(int i = 0 ; i < arr.length ; i++){ //數(shù)組元素,被查找的元素比較 if(arr[i] == key){ //返回索引 return i; } } return -1; } }
