一、二维数组
1.二维数组英文名：two dimension array
2.二维数组定义：
（1）初始化：
①动态数组： int[][] arr=new int[2][3];
②静态数组： int[][] arr={
{1,2,3,4},{2,1,6,5}};
③特殊的二位数组声明方式：int[]arr[]=new int[2][3];
（2）定义：二维数组中的每个元素又是一个一维数组
注意：每个一维数组的长度不一定相等
3.获取二维数组的长度（length属性）：
int[][] arr={
{1,2,3,4},{2,1,6,5}};
//遍历二维数组中的每个元素
for(int i=0;i<arr.lengrh;i++){//arr.length获取二维数组中元素的个数（一维数组的个数）
//遍历二维数组中的一维数组中的元素
for(int j=0;j<arr[i].length;j++){//arr[i].length获取二维数组中的每个元素的长度（一维数组的长度）
Sysem.out.print(a[i][j]);//输出二维数组中的每一个元素（输出一维数组）
}
Sysem.out.println();//换行
}
Sysem.out.println(a[1][2]); //输出的是第2个二维数组中的第3个元素：6
4.二维数组的存储结构：
（1）二维数组的初始化结构：
（2）二维数组的中赋值arr[1][1]=8(二维数组中第二个一维数组的第2个赋值为：8)：
5.杨辉三角：
（1）规律：arr[i][j]=arr[i-1][j]+arr[i-1][j-1];
（2）注意：当j=0或者j=arr[i].length-1时：arr[i][j]=1;
package guanqiawu;
import java.util.Scanner;
public class two_2_1 {
public static void main(String[] args) {
Scanner sr=new Scanner(System.in);
System.out.print("请输入你想打印的杨辉三角行数：");
//int a=sr.nextInt();
int [][]b=new int[sr.nextInt()][];
for(int i=0;i<b.length;i++){
b[i]=new int[i+1];
for(int j=0;j<b[i].length;j++){
if(j==0||j==b[i].length-1){
b[i][j]=1;
}else{
b[i][j]=b[i-1][j]+b[i-1][j-1];
}
if(j==b[i].length-1){
System.out.println(b[i][j]);
}else {
System.out.print(b[i][j]+" ");
}
}
}
}
}
二、排序
1.comparable接口：
（1）成员变量定义方法：private string esername；//学生类的姓名；private string age；//学生类的年龄
2.冒泡排序：
（1）原理：两个相邻之间的元素进行比较，前一个元素小于后一个元素就将较大的放在后面的位置
（2）类名：bubble
（3）构造方法：Bubble()//创建Bubble对象
（4）成员方法：
①public static void sort(Comparable[] a);{//对数组内的元素进行排序
for(int i=a.length-1;i>0;i–){
for(int j=0;j<i;j++){
//比较索引j和索引j+1处的值
if(greater(a[j],a[j+1])){
exch(a,j,j+1);
}
}
}
}
②private staric boolean greater(Comparable v,Comparable w);{//判断v是否大于w
int result = v.compareTo(w);//当result>0,则v>m;当result=0,则v=m;当result,则v<m
//return v.compareTo(w)>0;
return false；
}
③private static void exch(Comparable[] a,int i,int j);{//交换a数组中，索引i和索引j处的值
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
（5）元素比较次数：n^2/2-n/2;
（6）元素交换次数：n^2/2-n/2;
（7）总执行次数：(n^2/2-n/2)+(n^2/2-n/2)=n^2-n;
（8）按照大o的推导法则，保留函数中的最高阶顶那么最终冒泡排序的时间复杂度为O(n^2).
（9）适用场景：数据较少时
package guanqiawu;
import java.util.Arrays;
public class maopao {
public static void main(String[] args){
int []a={8,6,10,9,5,7};
for(int i=0;i<a.length-1;i++){//i=0时选出最大的放在最后；i=1时选择第二大的放在最后以此类推
for(int j=0;j<a.length-i-1;j++){//选出最大的元素
if(a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
System.out.println(Arrays.toString(a));
}
}
注意：Arrays.toString(数组名)是将数组转换成String类型输出
3.选择排序：
（1）原理：每一次遍历中，都假定第一个索引处的元素是最小值，和其他索引处的值依次比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后找到最小值所在的索引； 交换第一个索引处和最小值所在的索引处的值
（简单说就是先找出元素中索引的最小元素，然后与第一个开始索引的值交换位置；其后面的索引次数减一）
（2）类名：Selection
（3）构造方法：Selection():创建Selection对象
（4）成员方法：
①public static void sort(Comparable[] a):对数组内的元素进行排序
for(int i=0;i<=a.length-2;i++){
//定义一个变量，记录最小元素所在的索引，默认为参与选择排序的第一个元素所在的位置
int min=i;
for(int j=i+1;j<a.length;j++){
//需要比较最小索引min处的值与j索引处的值
if(greater(a[min],a[j])){
min=j;
}
}
exch(a,i,min);//交换最小元素索引min处的值和j索引处的值
}
}
②public static boolean greater(Comparable v,Comparable w):判断v是否大于w
int result = v.compareTo(w);//当result>0,则v>m;当result=0,则v=m;当result,则v<m
//return v.compareTo(w)>0;
return false；
}
③private static void exch(Comparable[] a,int i,int j):交换a数组中，索引i和索引j处的值
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
package guanqiawu;
import java.util.Arrays;
public class xuanze {
public static void main(String[] args) {
int[]b={12,6,8,9,10,32,45,0,1,4};
int a=0;
for(int i=0;i<b.length-1;i++){
for(int j=i+1;j<b.length;j++){
if(b[i]>b[j]){
a=j;
}else{
continue;
}
int min=b[i];
b[i]=b[a];
b[a]=min;
}
}
/* System.out.println(Arrays.toString(b));
for(int i=0;i<b.length-1;i++){
if(b[i]>b[i+1]){
a=i+1;
}
int min=b[a];
b[a]=b[i];
b[i]=min;
}
System.out.println(Arrays.toString(b));*/
}
}
//for循环的嵌套使用，外层完成了数据交换，内层循环完成了数据比较
（5）比较次数：n^2/2-n/2;
（6）数据交换次数：n-1
（7）时间复杂度：n^2/2-n/2+(n-1)=n^2/2+n/2-1;
根据大O推导法则，保留最高阶顶，去除常数因子，时间复杂度为O(n^2)
4.插入排序：
（1）原理：把所有元素分为两组，已经排序和未排序的；找到未排序的组中的第一个元素，向已经排序的组中进行插入；倒序遍历已经排序的元素，依次和插入的元素进行比较，直到找到一个元素小于等于待插入的元素，那么就把待插入的元素放到这个位置，其他的元素向后移动一位。
（2）类名：Insertion
（3）构造方法：Insertion（）；创建Insertion对象
（4）成员方法：
①public static void sort(Comparable[] a):对数组内的元素进行排序
for(int i=1;i<a.length;i++){
for(int j=1;j>0;j–){//比较j索引处的值和j-1处的值，如果索引j-1处的值比索引j处的值大，则交换数据，如果不大，那么就找到了合适的位置，退出循环即可；
if (greater(a[j-1],a[j])){
exch(a,j-1,j);
}else{
break;
}
}
}
②public static boolean greater(Comparable v,Comparable w):判断v是否大于w
int result = v.compareTo(w);//当result>0,则v>m;当result=0,则v=m;当result,则v<m
//return v.compareTo(w)>0;
return false；
}
③private static void exch(Comparable[] a,int i,int j):交换a数组中，索引i和索引j处的值
Comparable temp;
temp = a[i];
a[i]=a[j];
a[j]=temp;
}
（5）比较次数：n^2/2-n/2;
（6）数据交换次数：n^2/2-n/2;
（7）时间复杂度：（n^2/2-n/2）+(n^2/2-n/2;)=n^2-n;
根据大O推导法则，保留最高阶顶，去除常数因子，时间复杂度为O(n^2)
package guanqiawu;
import java.util.Arrays;
public class charu {
public static void main(String[] args) {
int[]a={21,3,1,23,2,5,65,10,86,15,7};
for(int i=1;i<a.length;i++){
int b=a[i];
while (i-1>=0&&b<=a[i-1]){
a[i]=a[i-1];
i--;
}
a[i]=b;
/* if(a[i]<=a[i-1]){
int j=0;
for( j=i;j>=0;j--){
a[j]=a[i-1];
}
a[j]=b;
}*/
}
System.out.println(Arrays.toString(a));
}
}
5.快速排序：
（1）原理：
①先从元素中取出一个数作为基准；
②分区：将比基准数大的放在右边，小于等于基准数的放大左边；
③在对左右两边的区中的数重复第二步，直到各个区间只有一个数
注意：一般默认的基准数是在最左边，所以首先从右边开始比较，如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
package guanqiawu;
import java.util.Arrays;
public class kuaisu {
/**
* 分区过程
* a[] 待分区数组
* left 待分区数组最小下标
* right 待分区数组最大下标
*/
public static void kuaisu(int[] a,int left,int right) {
if(left<right) {
int temp=qSort(a,left,right);
kuaisu (a,left,temp-1);
kuaisu (a,temp+1,right);
}
}
/**
* 排序过程
* a 待排序数组
* left 待排序数组最小下标
* right 待排序数组最大下标
* @return 排好序之后基准数的位置下标，方便下次的分区
*/
public static int qSort(int[] a,int left,int right) {
int temp=a[left];//定义基准数，默认为数组的第一个元素
while(left<right) {//循环执行的条件
//因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
//如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
while(left<right && a[right]>temp) {
right--;
}
//跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
//这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
if(left<right) {
a[left++]=a[right];
}
//下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
//因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
while(left<right && a[left]<=temp) {
left++;
}
//跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
if(left<right) {
a[right--]=a[left];
}
}
//当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
//这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
a[left]=temp;
return left;
}
public static void main(String[] args) {
int[] a= {72,6,57,88,60,42,83,73,48,85};
kuaisu (a,0,9);
System.out.println(Arrays.toString(a));
}
}