### 一维数组
什么是数组？
数组可以存放多个同一类型数据。
### 一、关于数组的声明有两种：
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)
