[数据结构与算法]ZJTD准备

1、Java中JDK的是干啥的？

JDK是Java的开发工具，它不仅提供了Java程序运行所需的JRE，还提供了一系列的编译，运行等工具，如javac，java，javaw等。JRE只是Java程序的运行环境，它最核心的内容就是JVM（Java虚拟机）及核心类库。

2、排序算法以及时间复杂度

冒泡：
刚开始交换的范围是0-N-1，第一个和第二个比较，大于就交换，再比第二个和第三个，依次进行，最大的数会放在数组最后的位置。然后把范围放到0-N-2，数组第二大的数会放在数组倒数第二的位置。依次进行整个交换过程，最后范围只剩一个数时，数组有序。

O(n^2)

直接选择排序：
一开始在0-N-1区间上选择一个最小值，放在位置0上，然后在1-N-1范围上选一个最小的放在位置1上，重复过程直到剩下最后一个元素。

O(n^2)

直接插入排序：

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

O(n^2)

快速排序

快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边部分，大于此数的放在右边部分，这个操作确保了这个数是处于正确位置的，再对左边部分数组和右边部分数组递归调用快速排序，重复这个过程。

O(nlogn)

堆排序

堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素? ?建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。

O(nlogn)

归并排序

首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，得到长度为2的有序区间，依次进行，直到合成整个区间。

O(nlogn)

桶排序

桶排序是计数排序的变种，把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。

Arrays.sort底层的排序算法

三个阈值：

1、length<286 -> length < 47 插入排序

? ? ? ? ? ? ? ? ? ? ? ? ? -> length > 47 快排

? ? ? length>286 -> 判断数组具不具备结构，每遇到一个降序组，计数+1，大于67快排

? ? ? 小于并归

进程切换

无论是在多核还是单核系统中，一个CPU看上去都像是在并发的执行多个进程，这是通过处理器在进程间切换来实现的。

• 操作系统实现这种交错执行的机制称为上下文切换。
• 操作系统保持跟踪进程运行所需的所有状态信息，这种状态，也就是上下文，它包括许多信息，例如PC和寄存器文件的当前值，以及主存的内容。

在任何一个时刻，单处理器系统都只能执行一个进程的代码。

当操作系统决定要把控制权从当前进程转移到某个新进程时，就会进行上下文切换，即保存当前进程的上下文，恢复新进程的上下文，然后将控制权传递到新进程，新进程就会从上次停止的地方开始。

内核为每一个进程维持一个上下文。上下文就是内核重新启动一个被抢占的进程所需的状态。包括一下内容：

• 通用目的寄存器
• 浮点寄存器
• 程序计数器
• 用户栈
• 状态寄存器
• 内核栈

• 各种内核数据结构：比如描绘地址空间的页表，包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表。

• 进程切换

  系统中的每个程序都是运行在某个进程的上下文中的。
  　　上下文是由程序正确运行所需的状态组成的，这个状态包括存放在存储器中的程序的代码和数据，他的栈，通用目的寄存器的内容，程序计数器，环境变量以及打开文件描述符的集合。

  所以进程切换就是上下文切换。

  ?那回到最开始的问题，进程切换和线程切换有什么区别？

  当然这里的线程指的是同一个进程中的线程。要想正确回答这个问题，需要理解虚拟内存。

  虚拟内存

  虚拟内存是操作系统为每个进程提供的一种抽象，每个进程都有属于自己的、私有的、地址连续的虚拟内存，当然我们知道最终进程的数据及代码必然要放到物理内存上，那么必须有某种机制能记住虚拟地址空间中的某个数据被放到了哪个物理内存地址上，这就是所谓的地址空间映射，那么操作系统是如何记住这种映射关系的呢，答案就是页表。

  每个进程都有自己的虚拟地址空间，进程内的所有线程共享进程的虚拟地址空间。

  现在我们就可以来回答这个面试题了。

  进程切换和线程切换的区别

  最主要的一个区别在于进程切换涉及虚拟地址空间的切换而线程不会。因为每个进程都有自己的虚拟地址空间，而线程是共享所在进程的虚拟地址空间的，因此同一个进程中的线程进行线程切换时不涉及虚拟地址空间的转换。

  有的同学可能还是不太明白，为什么虚拟地址空间切换会比较耗时呢？

  现在我们已经知道了进程都有自己的虚拟地址空间，把虚拟地址转换为物理地址需要查找页表，页表查找是一个很慢的过程，因此通常使用Cache来缓存常用的地址映射，这样可以加速页表查找，这个cache就是TLB（translation Lookaside Buffer，我们不需要关心这个名字只需要知道TLB本质上就是一个cache，是用来加速页表查找的）。由于每个进程都有自己的虚拟地址空间，那么显然每个进程都有自己的页表，那么当进程切换后页表也要进行切换，页表切换后TLB就失效了，cache失效导致命中率降低，那么虚拟地址转换为物理地址就会变慢，表现出来的就是程序运行会变慢，而线程切换则不会导致TLB失效，因为线程线程无需切换地址空间，因此我们通常说线程切换要比较进程切换块，原因就在这里。