1.数组
定义：
可以同时存储多个相同类型的数据,他是引用数据类型.
new：
堆区是动态开辟空间。在堆内开辟空间，返回数组的地址。
创建示例
构成:new + 数据类型 + [元素的个数]
//new :在堆内开辟空间,将数组的地址返回
//int代表元素的数据类型
//[3]:代表数据的个数
//我们可以通过一个变量保存数组的地址,这个变量的类型是int型的数组类型.
//注意:int+[]是一个整体,代表一种数据类型,不能拆开.[]中也不能写数.
int[] arr = new int[3];数组的内存
声明变量时，保存的地址，有默认值。
工作的是对象，进行赋值。
数组的内存空间是连续的,并且空间创建之后是固定的.
在定义变量时叫初始化。其他叫赋值。
其他的创建数组的方法
//创建数组并初始化
//new int[这里什么都不能写] {就是数组的元素} 这里的数量就是元素的个数
int[] arr1 = new int[] {4,5,7};
//直接写{} 注意:这种方法是在内部进行的new
int[] arr2 = {5,7,9,9};数组的遍历
遍历:将数组的所有元素都打印出来
arr.length数组的长度(元素的个数)
for(int i=0;i<arr.length;i++) {
System.out.println(arr[i]);
}数组越界异常
如果下标超出了数的范围,会报下标越界异常java.lang.ArrayIndexOutOfBoundsException
数组和函数的联合应用
数组往往作为函数的参数来实现某个功能。
2.值传递和址传递
值传递:将保存简单数据的变量作为参数传递 址传递:将保存地址的变量作为参数传递
3.二维数组
一维数组:直接存储了一组数的数组
二维数组:直接存储的是多个一维数组(的地址)的数组
数组的空间都是连续的,并且是固定的.
组成:new + 数据类型+[一维数组的个数]+[每个一维数组中元素的个数]
注意点:第一个[]中的数不能省,第二个[]中的数可以省略.写了,代表每个一维数组中元素的个数.不过这个数是一个估值.
int[][] arr2 = new int[3][4];
//赋值:
arr1[0] = 3;
arr2[0] = new int[3];
arr2[1] = new int[] {3,4,5};
arr2[2] = new int[3];//数组的创建
//这种方式不能创建二维数组
//int arr3 = new int {4,5,3};
//这样写可以
int arr4 = {{4,5,6},{3,4}};4.排序
几种排序方法:
冒泡,选择,希尔,快速排序,归并排序,插入排序
各算法的时间复杂度
平均时间复杂度
插入排序 O(n2) 冒泡排序 O(n2) 选择排序 O(n2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n1.25)
4.1冒泡排序
//冒泡排序:先确定最大值
public static void bubbleSort(int[] arr) {
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]) {//交换---改结束值
arr[j] = arr[j] ^ arr[j+1];
arr[j+1] = arr[j] ^ arr[j+1];
arr[j] = arr[j] ^ arr[j+1];
}
}
}
}4.2选择排序
//选择排序:先确定最小值
public static void SelectedSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {//确定的是整体的次数,比元素的个数少一
for (int j = i; j < arr.length-1; j++) {//确定一个元素需要比较的次数
if (arr[i] > arr[j+1]) {//交换---改起始值
arr[i] = arr[i] ^ arr[j+1];
arr[j+1] = arr[i] ^ arr[j+1];
arr[i] = arr[i] ^ arr[j+1];
}
}
}
}4.3插入排序
public class 插入排序 {
public static void main(String[] args) {
int[] arr = {6,2,7,3,8,9};
System.out.println(Arrays.toString(insertionSort(arr)));
}
public static int[] insertionSort(int[] arr) {
int preIndex, current;
for (int i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
} 4.4归并排序
算法思路
想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
1.两路归并排序算法思路
①把 n 个记录看成 n 个长度为1的有序子表
②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
③重复第②步直到所有记录归并成一个长度为 n 的有序表为止
直白的所就是分为两个步骤
现将数组中的元素拆分成一个一个的子集,使用合并将子集变成有序
拆分是很简单的操作,每次都按照原有的数组元素进行一半拆分 开始元素的位置+最后一个元素的位置/2
如何将将二个有序数列合并。只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
代码
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] array = new int[10];
for(int i = 0;i<array.length;i++){
array[i] = (int)(Math.random()*100);
}
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
// 将数组拆分为两份，并递归拆分子数组，直到数组中只有一个元素
mergeSort(array, left, center);
mergeSort(array, center + 1, right);
// 合并相邻数组
merge(array, left, center, right);
}
}
// 合并子数组的函数
public static void merge(int[] array, int left, int center, int right) {
// 临时数组，用于排序
int[] tempArray = new int[array.length];
// 用于将排好序的临时数组复制回原数组
int mark = left;
// 第二个数组的左端
int mid = center + 1;
// 用于临时数组的下标
int tempLeft = left;
while (left <= center && mid <= right) {
// 从两个子数组中取出最小的放入临时数组，即按从小到大的顺序重新排布
if (array[left] <= array[mid]) {
tempArray[tempLeft++] = array[left++];
} else {
tempArray[tempLeft++] = array[mid++];
}
}
// 剩余部分依次放入临时数组
while (left <= center) {
tempArray[tempLeft++] = array[left++];
}
while (mid <= right) {
tempArray[tempLeft++] = array[mid++];
}
// 将中间数组中的内容复制回原数组
while (mark <= right) {
array[mark] = tempArray[mark++];
}
}
}4.5快速排序
快速排序，顾名思义，是一种速度快，效率高的排序算法。
快排原理：
在要排的数（比如数组array）中选择一个中心值key（比如array[0]），通过一趟排序将数组array分成两部分，其中以key为中心，key右边都比key大，key左边的都key小，然后对这两部分分别重复这个过程，直到整个有序。
整个快排的过程就简化为了一趟排序的过程，然后递归调用就行了。
一趟排序的方法：假设要排的数组为：array[8] ={ 5 2 8 9 2 3 4 9 }
选择 key = 5， 开始时 i=0，j=7
index 0 1 2 3 4 5 6 7
开始： 5 2 8 9 2 3 4 9
i j
第一次找 5 2 8 9 2 3 4 9
i j
交换： 5 2 4 9 2 3 8 9
i j
第二次找 5 2 4 9 2 3 8 9
i j
交换： 5 2 4 3 2 9 8 9
i j
第三次找 5 2 4 3 2 9 8 9
ij
调整key： 2 2 4 3 5 9 8 9
第1步：找基准值
所谓的基准值，顾名思义就是以它为基准进行比大小。通常来说，我们选取数组的第一个数为基准值。在数组array里基准值就是5.
第2步：比大小
先从数组的最右边开始往左边找比基准值小的第一个数，然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢？因为现在我们要把数组从小到大排序，所以要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。
那么在数组array里，从左往右找，第一个比5大的数就是8，我们把它的坐标记为i；从右往左找，第一个比5小的数就是4，我们把它的坐标记为j。
第3步：交换
找到之后，如果这个时候i<j，那么就交换这两个数，因为i=2,j=6，符合条件，将4和8进行交换。现在数组变成了int[]a={5,2 ,4 ,9 ,2 ,3 ,8 ,9};
如果j>=i，那么不做处理
为什么还要判断i和j的大小呢？就像第二步说的，我们要找出比基准值小的数放到基准值的左边，找出比基准值的数放在基准值的右边。所以如果i<j的话，交换就达到目的了，如果i>=j，比基准值小的数就在基准值的左边，比基准值大的数已经在基准值的右边了，这时候就没必要交换了。
第4步：继续查找
在i<j的前提下，继续向右查找比基准值大的数，往左找比基准值小的数，然后交换。
在我们的例子中，9和3、符合交换的条件，所以数组就变成了
int[]a={5,2 ,4 ,3,2 ,9,8 ,9};这时候i=3,j=5
第5步：交换基准值到合适的位置
当查找继续进行，这时候i=j=4，已经不满足继续查找和交换的条件了，那么我们应该怎么办呢？答案就是把array[4]和基准值交换，因为i=j的时候说明已经到了一个分界线的位置，分界线左边的数比基准值小，分界线右边的数比基准值大，而这个分界线就是我们的基准值，所以把它和array[i]交换，这时候数组就变成：
int[]a={2,2 ,4 ,3,5 ,9,8 ,9};
第6步：重复
对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。
代码
import java.util.Arrays;
public class QuickSort {
public static void main(String[] arrayrgs) {
//创建数组
int[] array = new int[10];
for(int i = 0;i<array.length;i++){
array[i] = (int)(Math.random()*100);
}
System.out.println(Arrays.toString(array));
//调用排序
quickSort(array, 0 , array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int[] array, int start, int end) {
//1,找到递归算法的出口
if( start > end) {
return;
}
//2, 存储开始和末尾的位置
int i = start;
int j = end;
//3,存储基准值
int key = array[start];
//4，完成一趟排序
while( i< j) {
//4.1 ，从右往左找到第一个小于key的数
//要想降序只需要将> 修改成<
while(i<j && array[j] > key){
j--;
}
// 4.2 从左往右找到第一个大于key的数
//要想降序只需要将<= 修改成 >=
while( i<j && array[i] <= key) {
i++;
}
//4.3 交换
if(i<j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
// 4.4，调整key的位置
int p = array[i];
array[i] = array[start];
array[start] = p;
System.out.println(i);
//5, 对key左边的数快排
quickSort(array, start, i-1 );
//6, 对key右边的数快排
quickSort(array, i+1, end);
}
} 4.6希尔排序:
1、基本思想：
希尔排序也成为“缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，
使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，
最后在对所有元素进行一次直接插入排序。因此，我们要采用跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，
这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
希尔排序是对直接插入排序算法的优化和升级。
所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，
例如｛2,1,3,6,4,7,5,8,9,｝就可以称为基本有序了。但像｛1,5,9,3,7,8,2,4,6｝这样，
9在第三位，2在倒数第三位就谈不上基本有序
2、复杂度分析：
希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，
实现跳跃式移动，使得排序的效率提高。需要注意的是，增量序列的最后一个增量值必须等于1才行。
另外，由于记录是跳跃式的移动，希尔排序并不是一种稳定的排序算法。
3.代码
public class ShellSort {
**public** static void main(String[] args) {
**int**[] arr = {6,2,7,3,8,9};
*shellSort*(arr);
System.out.println(Arrays.toString(arr));
}
**public** static void shellSort(int[] data)
{
**int** j = 0;
int temp = 0;
for (int increment = data.length / 2; increment > 0; increment /= 2)
{
System.out.println("increment:" + increment);
for (int i = increment; i < data.length; i++)
{
// System.out.println("i:" + i);
temp = data[i];
for (j = i - increment; j >= 0; j -= increment)
{
// System.out.println("j:" + j);
// System.out.println("temp:" + temp);
// System.out.println("data[" + j + "]:" + data[j]);
if (temp < data[j]) {
data[j + increment] = data[j];
} else {
break;
}
}
data[j + increment] = temp;
}
}
}
}4.7基数排序
算法过程
- 初始化：构造一个10*n的二维数组，一个长度为n的数组用于存储每次位排序时每个桶子里有多少个元素。
- 循环操作：从低位开始（我们采用LSD的方式），将所有元素对应该位的数字存到相应的桶子里去（对应二维数组的那一列）。然后将所有桶子里的元素按照桶子标号从小到大取出，对于同一个桶子里的元素，先放进去的先取出，后放进去的后取出（保证排序稳定性）。这样原数组就按该位排序完毕了，继续下一位操作，直到最高位排序完成。
下面给出一个实例帮助理解：
我们现有一个数组：73, 22, 93, 43, 55, 14, 28, 65, 39, 81
下面是排序过程（二维数组里每一列对应一个桶，因为桶空间没用完，因此没有将二维数组画全）：
1.按个位排序
0 1 2 3 4 5 6 7 8 9
81 22 73 14 55 28 39
93 65
43
按第一位排序后数组结果：
81,22,73,93,43,14,55,65,28,39
可以看到数组已经按个位排序了。
2根据个位排序结果按百位排序
0 1 2 3 4 5 6 7 8 9
14 22 39 43 55 65 73 81 93
28
取出排序结果：
14,22,28,39,43,55,65,73,81,93
可以看到在个位排序的基础上，百位也排序完成（对于百位相同的数子，如22,28，因为个位已经排序，而取出时也保持了排序的稳定性，所以这两个数的位置前后是根据他们个位排序结果决定的）。因为原数组元素最高只有百位，原数组也完成了排序过程。
代码
package sort;
public class RadixSort {
private static void radixSort(int[] array,int d)
{
int n=1;//代表位数对应的数：1,10,100...
int k=0;//保存每一位排序后的结果用于下一位的排序输入
int length=array.length;
int[][] bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里
int[] order=new int[length];//用于保存每个桶里有多少个数字
while(n<d)
{
for(int num:array) //将数组array里的每个数字放在相应的桶里
{
int digit=(num/n)%10;
bucket[digit][order[digit]]=num;
order[digit]++;
}
for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果
{
if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中
{
for(int j=0;j<order[i];j++)
{
array[k]=bucket[i][j];
k++;
}
}
order[i]=0;//将桶里计数器置0，用于下一次位排序
}
n*=10;
k=0;//将k置0，用于下一轮保存位排序结果
}
}
public static void main(String[] args)
{
int[] A=new int[]{73,22, 93, 43, 55, 14, 28, 65, 39, 81};
radixSort(A, 100);
for(int num:A)
{
System.out.println(num);
}
}
}4.8堆排序
https://www.cnblogs.com/developerY/p/3319618.html
5.查找
查找的条件:1.当有多个相同的值时,只查出现的第一个,查到了立刻停止查找
* 2.查到了,返回当前元素的下标
* 3.查不到,返回-1普通查找就是遍历一遍
二分查找
前提:数组必须是有序的
//二分查找
public static int binarySearch(int[] arr,int key) {
int l = 0;
int h = arr.length-1;
int m ;
while (l<=h) {
m = (l+h)>>1;//这里使用移位运算符做除法
if (key == arr[m]) {
return m;
}else if (key > arr[m]) {
l = m+1;
}else if (key < arr[m]) {
h = m-1;
}
}
return -1;//没有找到
}6.面向对象
面向对象是思想。三大特性:封装，继承，多态。
面向对象是相对于面向过程而言的。
面向对象是比面向过程更高级的一种思想。
面向对象是风符合人类思考习惯的思想。
面向对象可以让开发者从执行者变成指挥者。
面向过程执行速度更快。
面向对象的三要素----最好都写英文
- 名字:遵守大驼峰原则,所有单词的首字母大写
- 属性:成员变量:遵守小驼峰原则
- 行为:成员方法,遵守小驼峰原则
7.对象-类的实例
拥有相同或相似的属性和行为的对象可以提取出一个类
8.匿名对象
//匿名对象的作用:节省代码,节省内存
//应用场景:作为参数传递
//实例:每new一次,都会开辟一块儿新的空间
new Dog().age = 10;
new Dog().age = 20;
new Dog().name = "哈士奇";
System.out.println(new Dog().name+" "+new Dog().age);// 输出结果null 0
}9.类
当类调用静态成员变量时，字节码文件进行工作。字节码文件是个对象。
一个类型一旦创建出来,就是一个独立的数据类型,在他可见的范围内都是可以使用的,包括自己的内部.
class Person1{
String name;
Dog1 dog1;//组合
//一个类型一旦创建出来,就是一个独立的数据类型,在他可见的范围内都是可以使用的,包括自己的内部.
Person1 baby;//组合
public void test(Dog1 dog1) {//传参
}
}成员变量和局部变量
/*
- 总结成员变量的特点:
- 1.在创建对象的时候会赋默认值
- 2.可以在类中定义变量的时候,直接赋值
- 3.非静态的成员变量可以在除了static修饰的方法外任何地方使用.
- *成员变量和局部变量的区别:
- 1.作用域:成员变量是整个对象.局部变量是从定义开始到所在的函数/if/for结束
- 2.默认值:成员变量会有默认值,局部变量没有默认值,要想使用必须先赋值
- 3.释放机制:成员变量跟对象保持一致,通过垃圾回收机制回收,局部变量使用完立即释放
- 4.存放的位置:成员变量放在堆区中的对象中,局部变量放在栈区中的方法中.
- 我们一般将成员分成两类:静态的成员(static)和非静态的成员
- 静态的成员:静态的成员变量和成员方法.------可以使用引用调用,也可以使用类名调用
- 非静态的成员:非静态的成员变量和成员方法.---只能使用引用调用
- static:这是一个关键字,被static修饰的成员就变成了静态的.具有保值功能
- 为什么可以直接通过类名调用静态的成员?
- 当成员被static修饰之后就变成了静态的,会在class生成的同时放在静态方法区中一份,而静态方法区的特点是内容会随着
程序的结束而释放,所以对象的创建与否不能影响他们的调用,所以可以直接使用类名调用
静态的成员方法和非静态的成员方法优先使用哪一个?
答:优先使用静态的成员方法
原因:静态的方法比非静态的效率高,节省内存.
注意:但是有一种情况例外:当方法中必须使用非静态的成员变量的时候,这时必须使用非静态的方法
总结:被static修饰的成员变量会变成静态的成员变量,成员方法会变成静态的成员方法.
*/
10.构造方法
this关键字作为构造方法使用时，只能放在当前方法的第一行。
/*
- 构造方法:调用的方式:类名+()
- 作用:对对象的属性进行初始化,如果我们自己不创建构造方法,系统会调用默认的无参构造方法
- 自己创建构造方法:
- 分类:
- 1.创建无参的构造方法:会将成员变量默认初始化成null/false/0
- 2.创建有参的构造方法:会将成员变量进行初始化并赋值,赋值成你传进来的参数
- 构造方法的基本构成:
- 修饰词 方法名字(参数列表){
- 方法体
- }
- 注意点:1.没有返回值这一项 2.方法名必须与当前的类名同名
- 使用构造方法的注意点:
- 1.一旦创建了自己的构造方法,就不会再去调用系统默认的构造方法
- 2.多个构造方法之间是重载的关系
- this:是一种引用数据类型,本身是一个关键字,代表的是当前的对象,保存的是当前对象的地址
- 场景:当我们想在当前类的内部拿到当前对象的引用时,可以使用this
- this的功能总结:
- 1.用来区分成员变量和局部变量
- 2.可以在构造方法内部调用其他重载的构造方法,提高代码的复用性,简化代码
- 注意点:
- //1.不能自己调用自己---死循环
- //2.不能相互调用,死循环
- //3.this充当构造方法时,必须放在第一行
- //4.this在作为方法的时候,只能充当构造方法,不能作为其他方法
- //5.this的使用范围就是当前类的内部
*/
11.代码块
代码块儿:
- 静态代码块儿:随着类的加载而加载,在整个程序执行过程中只执行一次,执行顺序优先于main
- 构成:static+{}
- 作用:对类进行初始化
- 构造代码块儿:随着对象的加载而加载,每次创建对象的时候都会执行一次,执行顺序优先于构造方法.
- 构成:{}
- 作用:对对象进行初始化
- */
12.封装性
定义：通过对具体属性的封装实现的.把对成员变量的访问进行私有化,通过公共的方法间接的实现访问
好处：提高了代码的安全性,复用性和可读性.
脏数据：我们把程序中出现的不符合逻辑的数据称为脏数据
/*
* 因为往往我们会有大量的属性需要进行赋值取值操作,所以就形成了一个规范
* 赋值的规范:set
* 构成:修饰词 返回值 方法名 (参数列表){
* 方法体中的代码
* return 返回值
* }
* 修饰词:一定是public
* 返回值:不需要,这里写void
* 方法名:set+属性的名字,名字的首字母大写
* 参数列表:一般只有一个,写法:与属性同名
* 代码:this.属性的名字 = 参数
* return:不需要
*
* 取值的规范:get
* 构成:修饰词 返回值 方法名 (参数列表){
* 方法体中的代码
* return 返回值
* }
* 修饰词:public
* 返回值:类型与属性一致
* 方法名:get+属性的名字,首字母大写
* 参数列表:不需要
* 代码:没有
* return 属性的名字/this.属性的名字
*/13.继承
多态的前提。
//对象调用方法的原理:首先会在自己的内部找这个方法,找到了直接使用,找不到会继续去父类中找,同理,找到了使用,停止查找,
//找不到继续向上找,一直找得到Object类,如果还没有找到,就认为没有这个方法
重写
重写方法的返回值可以与父类的相同，也可以是父类返回值类型的子类。
当父类与子类出现完全相同的方法的时候,我们称为重写
重写的时候,子类的同名方法会把父类的方法覆盖
作用:在实现方法原来功能的基础上实现一些自己特有的功能
构造方法
子类的构造方法，默认有一个super()；
子类无参构造方法，会默认调用父类无参的构造方法，如果不写，会调用系统默认的父类构造方法。
原因：构造方法是对属性的初始化。子类的构造方法无法对父类的属性进行初始化，所以先调用父类的构造方法。
- 继承中构造方法的使用
- -
- 1.当一个子类中只有一个带参数的构造方法,只能使用带参数的,不能使用无参的.如果想使用,必须手动建立无参的构造方法
- 2.当父类中只有带参数的构造方法,子类的构造方法中就必须在第一行手动调用父类带参数的构造方法(super(参数))
- 3.当我们创建构造方法的时候,如果自己不写super(),系统会自动调用
- 原因:父类中也有属性要进行初始化,而对象的属性必须由自己的构造方法进行初始化,所以必须调用super(),所以每个构造方法中都默认有一个super()
- 为什么要将super放在方法的第一行?
- 答:在子类的构造方法中有可能用到父类的属性,而属性在使用之前必须先进行初始化,否则无法使用.
- 总之:在继承体系中,作为父类最好的办法就是将无参构造方法和有参构造方法都写了.
- 注意:每次创建类时必须有的内容:1属性 2.get,set 3.有参无参构造方法 4.toString方法
- */
京公网安备 11010502036488号