2020-07-21
类加载的过程
#
- 加载
- 通过一个类的全限定名来获取定义此类的二进制字节流。
- 将这个字节流所代表的静态存储结构转化为方法去的运行时数据结构。
- 在内存中生成一个代表这个类的java.lang.Class对象，作为方法区这个类的各种数据的访问入口。
- 验证
- 确保Class文件的字节流对象中包含的信息符合当前虚拟机的要求，并且不会危虚拟机自身的安全。
- 准备
- 准备阶段是正式为类变量分配内存并设置类变量初始值（零值）的阶段，这些类变量使用的内存都将在方法区进行分配。
- 如果类变量同时也被final修饰了，那它就是一个常量，准备阶段就会被初始化为代码中指定的值。
- 解析
- 将常量池内的符号引用替换为直接引用的过程。
- 符号引用：以一组符号来描述所引用的目标，符号可以是任何形式的字面量，只要使用时能无歧义地定位到目标即可。
- 直接引用：可以是直接指向目标的指针、相对偏移量或是一个能间接定位到目标的句柄。
- 初始化
- 初始化时执行类构造器clinit的方法的过程。
- clinit方法是由编译器自动收集类中的所有类变量的赋值动作和静态语句块static{}中的语句合并产生的，编译器收集的顺序是由语句在源文件中出现的顺序所决定的。
- 定义在静态语句块之后的类变量，在该静态语句块中可以赋值，但不能访问。
class Main{
static{
i=0; //正常编译通过
System.out.println(i); //这句编译器会提示非法向前引用
}
static int i=1;
}
类加载器
#
- 启动类加载器Bootstrap ClassLoader
- 用来加载Java的核心类库（JAVA_HOME\lib目录或者被-Xbootclasspath参数所指定的路径中）。
- 没有父类加载器
- 加载扩展类和应用程序类加载器，并指定为它们的父类加载器。
- 扩展类加载器Extension ClassLoader
- 派生于ClassLoader，父类为Bootstrap。
- 从java.ext.dirs系统变量所指定的路径中加载所有类库。
- 应用程序类加载器Application ClassLoader
- 派生于ClassLoader，父类为扩展类加载器。
- 负责加载classspath下的类库。
- 程序中的默认类加载器。
双亲委派机制
#
- 如果一个类收到类加载请求，它首先不会自己去尝试加载这个类，而是把这个请求委派给父类加载器去完成。
- 如果父类还有父类，则进一步向上委托，请求最终到达顶层的启动类加载器中。
- 如果父类可以完成加载，就成功返回。否则，子类加载器才会尝试自己去加载。
2020-06-21
思想
#
大停，小停，大小交换，相遇时相遇点和基准点交换，以相遇点为界限展开递归
1、选取一个基准元素（star）
2、比star小的放到star左边，比star大的放到star右边
3、当上述步骤执行完成后，star的位置就不变了，它现在的位置就是它最终该放置的位置
4、对star左边所有元素进行1、2操作，对star右边元素进行1、2操作
代码实现
#
#include "sort.h"
static void swap(int *, int, int);
static void sort1(int *, int, int);
void sort(int *arr, int len)
{
sort1(arr,0, len - 1);
}
/*
大停，小停，大小交换，相遇时相遇点和基准点交换，以相遇点为界限展开递归
*/
static void sort1(int *arr, int start, int end)
{
if (start >= end)
{
return;
}
int star = arr[start];
int l = start, r = end;
while (l < r)
{
while ((arr[r] > star) && (l < r))
{
r--;
}
while ((arr[l] <= star) && (l < r))
{
l++;
}
if (l < r)
{
swap(arr, l, r);
}
else
{
swap(arr, start, l);
}
}
sort1(arr, start, l -1);
sort1(arr, l + 1, end);
}
static void swap(int *arr, int num1, int num2)
{
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
复杂度
#
平均时间复杂度：O(nlog₂n)
空间复杂度：O(log₂n)
不稳定的排序算法
2020-06-21
思想
#
1.将序列元素先分割成一个个单独的元素，由于只有一个元素，我们可以看作它是有序的
2.将上述的序列两两合并，并使得他们合并后的结果仍然有序
3.重复上述步骤，直到合成一个完整的序列
从实现上来看，有点像二叉树的后序遍历。
代码实现
#
public void mergeSort(int[] a,int low,int high){
//可以看到，当切割到只剩一个元素时，开始进行合并
if(low<high){
//找到数组中的中间点，把数组分为两部分
int mid=(low+high)/2;
//对左边进行mergeSort操作
mergeSort(a,low,mid);
//对右边进行mergeSort操作
mergeSort(a,mid+1,high);
//合并左右两部分
merge(a,low,mid,high);
}
}
void merge(int[] a,int low,int mid,int high){
for(int i=low;i<=high;i++){
//缓冲空间，
buf[i]=a[i];
}
//i，j分别是左指针和右指针
int i,j,k;
//比较左右两边的元素，谁小谁放在前面
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(buf[i]<=buf[j])
a[k]=buf[i++];
else if(buf[i]>buf[j])
a[k]=buf[j++];
}
//当一边全部比较完成后，另一边的元素就直接送到a的后面
while(i<=mid)
a[k++]=buf[i++];
while(j<=high)
a[k++]=buf[j++];
}
复杂度
#
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定的排序算法
2020-06-21
思想
#
第一趟从n个无序记录中选择关键字最小的记录与第1个记录交换，此时第一个记录为有序
第二趟从第二个记录开始的n-1个无序记录中选择关键字最小的与第2个记录交换，此时前两个记录有序
……
如此下去，直到无序序列只剩最后一个元素，排序结束
代码实现
#
public void selectSort(int[] a) {
for(int i=0;i<a.length;i++){
//记录最小元素的位置
int min=i;
//该循环来寻找最小元素的位置
for(int j=i+1;j<a.length;j++){
if(a[j]<a[min]){
min=j;
}
}
//交换第i个元素和最小元素
int temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
稳定的排序算法
2020-06-21
思想
#
特点是两两交换。
相邻的两个数比较，每次比较将大的数放到下面，一次循环后， 最大的数就在最下面了。
小数上冒，大数沉底。
经过第一趟排序后，最大的数就移到了最后面。
第二趟排序会将次大值移到倒数第二位。
以此类推，直到所有的数排好位置。
代码实现
#
#include <stdio.h>
void sort(int *a, int length);
int main()
{
int n[10] = {9, 4, 10, 43, 75, 14, 0, 12, 53, 71};
sort(n, 10);
for (int i = 0; i < 10; i++)
{
printf("a[%d] is %d\n", i, n[i]);
}
return 0;
}
void sort(int *a, int length)
{
for(int i = 0; i < length; i++)
{
for(int j = 1; j < length; j++)
{
if(a[j - 1] > a[j])
{
int tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
}
}
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
稳定的排序算法
2020-06-21
直接插入排序
#
思想
#
将记录集合分为有序和无序两部分，每次从无序序列中取一个记录加入有序序列中，使该有序序列仍然有序。重复该步骤，直到无序序列中的记录全部插入有序序列。
代码实现
#
public static void insertionSort(int[] a){
for(int i=1;i<a.length;i++){
int key=a[i];//记录当前i位置的值
int j=i-1;
//将大于key的值全部后移
while(j>=0&&a[j]>key){
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
稳定的排序算法
折半插入排序
#
思想
#
在将无序序列中的元素插入有序序列时，采用折半查找确定其位置，从而减少查找的次数
代码实现
#
for(int i=1;i<a.length;i++){
int key=a[i];
int low=0,high=i-1;
//加入一个折半查找，减少查找次数
while(low<=high){
int mid=(low+high)/2;
if(a[mid]>key)
high=mid-1;
else if(a[mid]<key)
low=mid+1;
}
int j;
for(j=i-1;j>=high+1;j--)
a[j+1]=a[j];
a[j+1]=key;
}
复杂度
#
与直接插入排序相同
2020-06-21
定义
#
节点均小于其左孩子节点和右孩子节点
左孩子节点均小于其左右孩子节点
右孩子节点均小于其左右孩子节点
……
代码实现
#
public void buildHeap(int[] n,int len){//建立初始堆
for(int i=len/2;i>=1;i--){
adjustHeap(n,i,len);
}
}
public void adjustHeap(int[] n,int s,int len){//调整堆
for(int i=2*s;i<=len;i*=2){
//如果出现左右孩子节点大于该s节点时，该位置无需调整
//否则，不仅需要调整该s节点，还需要进行向下调整
if(i<len&&n[i]>n[i+1])
i++;
if(n[s]<n[i])
break;
else{
n[0]=n[i];
n[i]=n[s];
n[s]=n[0];
s=i;
}
}
}
public void heapSort(int[] n,int len){//堆排序
for(int i=len;i>1;i--){
//将堆顶元素与最后一个元素调换位置
n[0]=n[i];
n[i]=n[1];
n[1]=n[0];
//将未排序的前i-1个元素重新调整为堆
adjustHeap(n,1,(i-1));
}
}
复杂度
#
建立堆的时间复杂度：O(n)
堆排序的时间复杂度：O(nlogn)
空间复杂度：O(1)
不稳定的排序算法
2020-06-21
思想
#
- 先将整个待排序列中的记录按照指定的下标进行分组，并对每个组内的记录采用直接插入法排序
- 然后依次减少下标量，即使每组包含的记录增多，再继续对每组组内的记录采用直接插入法排序
- 依此类推，当下标增量减少到1时，整个待排序记录序列已成为一组，但由于此前所做的直接插入排序工作，整个待排序记录序列已经基本有序，最终完成了排序
代码实现
#
for(int dk=n.length/2;dk>=1;dk=dk/2){ //增量因子
for(int i=dk;i<n.length;i++){ //下面的代码类似插入排序
if(n[i]<n[i-dk]){
int temp=n[i];
int j;
//比temp大的往后挪，直到遇到比temp更小的
for(j=i-dk;j>=0&&temp<n[j];j=j-dk)
n[j+dk]=n[j];
n[j+dk]=temp;//将temp放在停的位置上
}
}
}
复杂度
#
时间复杂度：O(n²)
空间复杂度：O(1)
不稳定的排序算法