### 一維數組
什么是數組？
數組可以存放多個同一類型數據。
?
### 一、關于數組的聲明有兩種：
1.Java方法:?`int[]?array;`
2.C/C++方法：`int?array[];`
?
### 二、關于數組的用法，有三種方式：
#### 1、常用法
##### 1、數組的定義
數據類型[]?數組名=new?數據類型[數組大小];
~~~
int[] a = new int[5];//定義一個數組名為a的整型數組，并可以放入5個整型數。
~~~
?
##### 2、數組的引用(使用)
數組名[下標]?
比如：使用a數組的第三個數a[2]
?
#### 2、先聲明在定義法
先聲明數組
語法：數據類型[]?數組名;??也可以??數據類型[]?數組名;
例：`int?a[];或者int[]?a;`
?
再創建數組
語法：數組名=new?數據類型[數組大小];
例：`a?=?new?int[10];`
?
數組的引用(使用)
數組名[下標]
例：引用a數組的第8個元素?a[7]?
?
數組的大小可以使用數組的length方法
語法：數組名.length
?
#### 3、初始化法(當已知元素值的時候可以使用此法)
##### 1、初始化數組
語法：數據類型[]?數組名={元素值,元素值...};
例：`int[]?a?=?{2,5,6,7,8,89,90,34,56}`
上面的用法相當于：
~~~
int[]?a?=?new?int[9]
int?a[0]?=?2;int?a[1]?=?5;int?a[2]?=?6;...a[8]?=?56;
~~~
?
##### 2、數組的引用(使用)
數組名[下標]
例：a數組的第8個元素a[7]
~~~
public class Test1 {
public static void main(String[] args) {
//定義一個可以存放六個float類型的數組
float[] arr=new float[6];
//使用for循環賦值
//給數組的各個元素賦值
arr[0]=3;
arr[1]=5;
arr[2]=1;
arr[3]=3.4f;
arr[4]=2;
arr[5]=50;
//計算總體重[遍歷數組]
float all=0;
for(int i=0;i<6;i++){
all+=arr[i];
}
System.out.println("總體重是："+all);
}
}
~~~
?
### 一維數組--小結
1、數組可存放同一類型數據；
2、簡單數據類型(int,float)數組，可直接賦值；
3、對象數組在定義后，賦值時需要再次為每個對象分配空間[即：new?對象]；(PS：這是因為對象數組，數組里面保存的是指向對象的指針)
4、數組大小必須事先指定；
5、數組名可以理解為指向數組首地址的引用；
6、數組的下標是從0開始編號的。
?
?
### 多維數組
多維數組以二維數組為例
### 1、定義
語法：類型[][]?數組名=new?類型[大小][大小];
比如：`int[][]?a=new?int[2][3];`
### 2、分析
二維數組在內存中存在的形式也是和一維數組一樣的，是線性的。并且二維數組int[][]?a=new?int[2][3];中?int[0],int[1]存儲的都是指向當前行的首地址
### 3、二維數組輸出如下圖形
0?0?0?0?0?0
0?0?1?0?0?0
0?2?0?3?0?0
0?0?0?0?0?0
~~~
public class Test2 {
public static void main(String[] args) {
int[][] a=new int[4][6];//定義二維數組a4行6列
a[1][2]=1;
a[2][1]=2;
a[2][3]=3;
//把圖形輸出
for(int i=0;i<4;i++){//控制行
for(int j=0;j<6;j++){//控制列
System.out.print(a[i][j]+"\t");//輸出數組
}
System.out.println();//換行
}
}
}
~~~
### 排序
### 排序的介紹
排序是將一堆數據，依指定的順序進行排列的過程。
?
### 排序分類：
1、內部排序法：指將需要處理的所有數據都加載到內部存儲器中進行排序。包括(交換式排序法、選擇式排序法和插入式排序法)；
2、外部排序法：數據量過大，無法全部加載到內存中，需要借助外部存儲進行排序。包括(歸并排序法和直接歸并排序法)。
?
?
#### 內部排序法--交換式排序法
交換式排序屬于內部排序法，是運用數據值比較后，依判斷規則對數據位置進行交換，以達到排序的目的。
交換式排序法又可分為兩種：
1、冒泡排序法(Bubble?Sorting)
2、快速排序法(Quick?Sorting)
?
##### 交換式排序法--冒泡排序法
????冒泡排序(Bubble?Sorting)的基本思想是：通過對待排序序列從后向前(從下標較大的元素開始)，依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼較小的元素逐漸從后部移向前部(從下標較大的單元移向下標較小的單元)，就象水底下的氣泡一樣逐漸向上冒。
????因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設置一個標志flag判斷元素是否進行過交換。從而減少不必要的比較。
**冒泡排序法10萬個數用時15秒**
~~~
//冒泡排序法
public class Test3 {
public static void main(String[] args) {
int arr[]={1,6,0,-1,9,-100,90};
int temp=0;
//排序
//外層循環，可以決定一共走趟
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]){
//換位
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]+"\t");
}
}
}
~~~
#### 選擇式排序法--選擇排序法
????選擇式排序也屬于內部排序法，是從欲排序的數據中，按指定的規則選出某一元素，經過和其他元素重整，再依原則交換位置后達到排序的目的。
選擇式排序又可分為兩種：
1、選擇排序法(Selection?Sorting)
2、堆排序法(Heap?Sorting)
?
????選擇排序(Select?Sorting)也是一種簡單的排序方法。它的基本思想是：第一次從R[0]-R[n-1]中選取最小值，與R[0]交換，第二次從R[1]-R[n-1]中選取最小值，與R[1]交換，第三次從R[2]-R[n-1]中選取最小值，與R[2]交換，...，第i次從R[i-1]-R[n-1]中選取最小值，與R[i-1]交換，...，第n-1次從R[n-2]-R[n-1]中選取最小值，與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。
例如，給定n=8，數組R中的8個元素的排序碼為：(8,3,2,1,7,4,6,5)，選擇排序過程。
**選擇排序法排序10萬個數用時7秒**
~~~
public class Test4{
public static void main(String []args){
int arr[]={8,3,2,1,7,4,6,5};
int temp=0;
for(int j=0;j<arr.length-1;j++){
//認為第一個數就是最小數
int min=arr[j];
//記錄最小數的下標
int minIndex=j;
for(int k=j+1;k<arr.length;k++){
if(min>arr[k]){
//修改最小值
min=arr[k];
minIndex=k;
}
}
//當退出for循環時就找到這次的最小值
temp=arr[j];
arr[j]=arr[minIndex];
arr[minIndex]=temp;
}
//輸出最后結果
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+"\t");
}
}
}
~~~
#### 插入式排序法--插入排序法
插入式排序屬于內部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當位置，以達到排序的目的。
插入式排序法又可分為3種：
1、插入排序法(Insertion?Sorting)
2、希爾排序法(Shell?Sorting)
3、二叉樹排序法(Binary-tree?Sorting)
?
插入排序(Insertion?Sorting)的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始有序表只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。
**插入式排序法排序10萬個數用時2秒**
~~~
public class Test5{
public static void main(String []args){
int arr[]={23,15,-13,62,5,-23,0,17};
for(int i=1;i<arr.length;i++){
int insertVal=arr[i];
//insertVal準備和前一個數比較
int index=i-1;
while(index>=0&&insertVal<arr[index]){
//將把arr[index]向后移動一位
arr[index+1]=arr[index];
//讓index向前移動一位
index--;
}
//將insertVal插入到適當位置
arr[index+1]=insertVal;
}
//輸出最后結果
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+"\t");
}
}
}
~~~
**交換式排序法--快速排序法**
快速排序(QuickSorting)是對冒泡排序的一種改進，由C.A.R.Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
**快速排序法排序1億數據用時14秒**
~~~
public class Test6 {
public static void main(String[] args) {
int[] a ={-1,-5,6,2,0,9,-3,-8,12,7};
QuickSort.quickSort(a, 0, a.length - 1);
for (int i : a) {
System.out.print(i + " ");
}
}
}
class QuickSort{
public static void quickSort(int[] array, int begin, int end){
int b = begin;
int e = end;
int m = array[(begin + end) / 2]; //中間值
int temp = 0; //臨時值
//當b < e時
while(b < e){
//從b開始正數找到一個大于m的值
while(array[b] < m){
b++;
}
//從e開始倒數找到一個小于m的值
while(array[e] > m){
e--;
}
if(b >= e){
break;
}
//兩邊都找到了符合的值，則交換
temp = array[b];
array[b] = array[e];
array[e] = temp;
//array[e]或者array[b]其中一個的值為m
//因為當前的array[e]的值已經跟m比較過了，所以--e;
if(array[b]== m){
--e;
}
//因為當前的array[b]的值已經跟m比較過了，所以++b;
if(array[e]== m){
++b;
}
}
if(b == e){
b++;
e--;
}
//左邊遞歸
if(begin < e){
quickSort(array, begin, e);
}
//右邊遞歸
if(end > b){
quickSort(array, b, end);
}
}
}
~~~
### 其它排序法--堆排序法
????將排序碼k1,k2,k3,...,kn表示成一棵完全二叉樹，然后從第n/2個排序碼開媽篩選，使由該結點組成的子二叉樹符合堆的定義，然后從第n/2-1個排序碼重復剛才操作，直到第一個排序碼止，這時候，該二叉樹符合堆的定義，初始堆已經建立。
????接著，可以按如下方法進行堆排序：將堆中第一個結點(二叉樹根結點)和最后一個結點的數據進行交換(k1與kn)，再將k1--kn-1重新建堆，然后k1和kn-1交換，再將k1--kn-2重新建堆，然后k1和kn-2交換，如此重復下去，每次重新建堆的元素個數不斷減1，直到重新建堆的元素個數僅剩一個為止。這時堆排序已經完成，則排序碼k1,k2,k3,...kn已排成一個有序序列。
????若排序是從小到大排列，則可以建立大根堆實現堆排序，若排序是從大到小排列，則可以用建立小根堆實現堆排序。
?
### 其它排序法--希爾排序法
????希爾排序(Shell?Sorting)又稱為“縮小增量排序”。是1959年由D.L.Shell提出來的。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列(由相隔某個“增量”的元素組成的)分別進行直接插入排序，待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進行一次直接插入排序。
?
### 其它排序法--二叉樹排序法
????二分插入排序(Binary?Insert?Sorting)的基本思想是：在有序表中采用二分查找的方法查找待排元素的插入位置。
????其處理過程：先將第一個元素作為有序序列，進行n-1次插入，用二分查找的方法查找待排元素的插入位置，將待排元素插入。
?
?
### 外部排序法
#### 其它排序法--歸并排序法(最為常用的排序方法)
????合并排序法(Merge?Sorting)是外部排序最常使用的排序方法。若數據量太大無法一次完全加載內存，可使用外部輔助內存來處理排序數據，主要應用在文件排序。
排序方法：
???將欲排序的數據分別存在數個文件大小可加載內存的文件中，再針對各個文件分別使用“內部排序法”將文件中的數據排序好寫回文件。再對所有已排序好的文件兩兩合并，直到所有文件合并成一個文件后，則數據排序完成。
1、將已排序好的A、B合并成E，C、D合并成F，E、F的內部數據分別均已排好序
2、將已排序好的E、F合并成G，G的內部數據已排好序
3、四個文件A、B、C、D數據排序完成
~~~
//合并排序法
public class Test7{
public static void main(String[] args)
{
Merge m=new Merge();
int a[]={5,4,10,8,7,9};
m.merge_sort(a,0,a.length-1);
}
}
class Merge{
//遞歸分成小部分
public void merge_sort(int[] arrays,int start,int end){
if(start<end){
int m=(start+end)/2;
merge_sort(arrays,start,m);
merge_sort(arrays,m+1,end);
combin_arrays(arrays,start,m,end);
}
}
//合并數組
public void combin_arrays(int[] arrays,int start,int m,int end){
int length=end-start+1;
int temp[]=new int[length];//用來存放比較的數組，用完復制回到原來的數組
int i=start;
int j=m+1;
int c=0;
while(i<=m &&j<=end){
if(arrays[i]<arrays[j]){
temp[c]=arrays[i];
i++;
c++;
}else{
temp[c]=arrays[j];
j++;
c++;
}
}
while(i<=m){
temp[c]=arrays[i];
i++;
}
while(j<=end){
temp[c]=arrays[j];
j++;
}
c=0;
for(int t=start;t<=end;t++,c++){
arrays[t]=temp[c];
}
snp(arrays);
}
//打印數組
public void snp(int[] arrays){
for(int i=0;i<arrays.length;i++){
System.out.print(arrays[i]+" ");
}
System.out.println();
}
}
~~~
### 查找
在java中，常用的查找方式有兩種：
### 1、順序查找(最簡單，效率最低)
### 2、二分查找
~~~
import java.util.*;
public class Test8 {
public static void main(String[] args) {
int arr[]={2,5,7,12,25};//定義arr數組并賦值
System.out.print("請輸入你需要查找的數：");
Scanner sr=new Scanner(System.in);
int a=sr.nextInt();
BinaryFind bf=new BinaryFind();//創建BinaryFind對象
bf.find(0,arr.length-1,a,arr);//調用find方法，并將數據傳給方法
}
}
//二分法
class BinaryFind{
public void find(int leftIndex,int rightIndex,int val,int arr[]){
//首先找到中間的數
int midIndex=((rightIndex+leftIndex)/2);
int midVal=arr[midIndex];
if(rightIndex>=leftIndex){
//如果要找的數比midVal大
if(midVal>val){
//在arr數組左邊數列中找
find(leftIndex,midIndex-1,val,arr);
}else if(midVal<val){
//在arr數組右邊數列中找
find(midIndex+1,rightIndex,val,arr);
}else if(midVal==val){
System.out.println("數組arr["+midIndex+"]中的數字是"+arr[midIndex]);
}
}else{
System.out.println("沒有找到你要找的數!");
}
}
}
~~~
### 遞歸
遞歸算法：是一種直接或者間接地調用自身的算法，其算法的流程走向必須形成封閉（即本身屬于廣義上的循環過程），否則遞歸將不能形成。在計算機編寫程序中，遞歸算法對解決很多類問題是十分有效，它使算法的描述簡潔而且易于理解。
?
遞歸算法的特點：
遞歸過程一般通過方法或子過程來實現。
遞歸算法：在方法或子過程的內部，直接或者間接地調用自己的算法。
遞歸算法的實質：是把問題轉化為規模縮小了的同類問題的子問題。然后遞歸調用方法(或過程)來表示問題的解。
?
遞歸算法解決問題的特點：
(1)遞歸就是在過程或方法里調用自身。
(2)在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
(3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低，即占用內存很大，有時這種情況用棧來代替解決。所以一般不提倡用遞歸算法設計程序。
(4)在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。
?
遞歸算法所體現的“重復”一般有三個要求：
一是每次調用在規模上都有所縮小(通常是減半)；
二是相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入)；
三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。
遞歸建議用在簡單的循環場合中,這種場合就是遞歸方法體只含IF-ELAE語句的情況，其余的復雜循環(甚至嵌套)情況建議不用遞歸,因為遞歸過程中所用到的變量都在遞歸結束前的過程中一直占用著內存,如果循環過程又趨于復雜則內存耗用量將顯著提升,運行速度也將下降.
###
### 二進制、位運算
### 二進制--基本概念
二進制是逢2進位的進位制，0、1是基本算符。
????現代的電子計算機技術全部采用的是二進制，因為它只使用0、1兩個數字符號，非常簡單方便，易于用電子方式實現。計算機內部處理的信息，都是采用二進制數來表示的。二進制(Binary)數用0和1兩個數字及其組合來表示任何數。進位規則是“逢2進1”，數字1在不同的位上代表不同的值，按從右至左的次序，這個值以二倍遞增。
注：1個字節=8位bit,
bit最高位是符號位如：■□□□□□□□黑色方框為符號位。
符號位0代表正數，1代表負數
?
### 二進制--原碼、反碼、補碼
對于有符號的而言：
1、二進制的最高位是符號位：0表示正數，1表示負數
2、正數的原碼、反碼、補碼都一樣
3、負數的反碼=它的原碼符號位不變，其它位取反
4、負數的補碼=它的反碼+1
5、0的反碼，補碼都是0
6、java沒有無符號數，換言之，java中的數都是有符號的
7、在計算機運算的時候，都是以補碼的方式來運算的。
?
### 位運算符和移位運算
java中有4個位運算，分別是“按位與&、按位或|、按位異或^，按位取反~”，它們的運算規則是：
按位與&：兩位全為1，結果為1
按位或|：兩位有一個為1，結果為1
按位異或^：兩位一個為0，一個為1，結果為1
按位取反~：0->1，1->0
~~~
~2=? //-3
2&3=? //2
2|3=? //3
~-5=? //4
13&7=? //5
5|4=? //5
-3^3=? //-2
~~~
注："~"代表位取反，"&"代表位與，"|"代表位或，"^"代表位異或
?
?
java中有3個移位運算符：
運算規則：
>>算術右移：低位溢出，符號位不變，并用符號位補溢出的高位
<<算術左移：符號位不變，低位補0
>>>邏輯右移：低位溢出，高位補0
~~~
public static void main(String []args){
int a=1>>2;
int b=-1>>2;
int c=1<<2;
int d=-1<<2;
int e=3>>>2;
//a,b,c,d,e結果是多少
System.out.println("a="+a);//a=0
System.out.println("b="+b);//b=-1
System.out.println("c="+c);//c=4
System.out.println("d="+d);//d=-4
System.out.println("e="+e);//e=0
}
~~~
注：">>"代表算術右移，"<<"代表算術左移，">>>"代表邏輯右移
?
----------參考《韓順平.循序漸進學.java.從入門到精通》
----------參考《JDK_API_1_6_zh_CN》
Java學習筆記--導航[http://blog.csdn.net/q547550831/article/details/49819641](http://blog.csdn.net/q547550831/article/details/49819641)
