八股文面试day1
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
二分查找解决整数溢出
方法一mid=(left+right)/2 -> left/2+right/2 -> left+(-left/2+right/2) -> l+(r-l)/2
方法二mid=(l+r)>>>1 字节溢出整体右移一位就是正确的值
MySQL存储引擎MyISAM和InnoDB的区别
- 数据的存储结构不同MyISAM在磁盘上存储有3个文件它们是以表的名字开头来命名的 .frm文件存储表定义 MYD文件存储数据文件 MYI文件存储索引文件InnoDB在磁盘上存储有2个文件 .frm文件存储表结构 .ibd文件存储数据和索引文件由于MyISAM的索引和数据是分开存储的因此在索引查找的时候MyISAM的叶子结点存储的是数据所在的地址而不是数据而InnoDB的叶子结点存储的是整个数据行所有的数据
- 存储空间的消耗不同MyISAM可能会被压缩存储空间也比较小它支持三种存储格式静态表、动态表和压缩表而InnoDB是需要更多的内存和存储它会在主内存中建立它专有的缓冲池用来去高速缓冲数据和索引所以InnoDB所在的表都保存在同一个数据文件中 InnoDB的表大小只受限于操作系统的文件大小 一般是2个GB
- 对事务的支持不同MyISAM强调的是性能每次查询都具有原子性它的执行速度比InnoDB要更快一些但是不支持事务操作而InnoDB除了事务支持外还支持外键等这样一些高级数据库的功能还具备事务提交事务回滚和崩溃修复能力这样的一些事务安全的类型的表
- 对锁的支持不同那如果是执行大量的查询MyISAM应该是更好的选择而MyISAM的增删改的时候需要去锁定整个表格所以它的效率会更低而InnoDB它是支持行级锁在删除插入的时候只需要锁定操作行就可以那如果有大量的插入、修改和删除的时候使用InnoDB它的性能会更高一些
- 对外键的支持不同MyISAM不支持外键而InnoDB是支持外键的不同的MySQL版本对两者的支持都有所改进的
常见的排序算法
冒泡排序
冒泡排序常规版优化方法bubble减少比较次数+冒泡次数重点加上标志
冒泡排序终极版优化方法bubble1记录最后一次交换位置减少比较次数+冒泡次数
文字描述依次比较数组中相邻两个元素大小 若a[j]>a[j+1] 则交换两个元素 两两比较一遍称为一轮冒泡结果是让最大的元素排到最后
package com.huhu.sort;
import java.util.Arrays;
public class BubbleSort2 {
public static void main(String[] args) {
int[] a={5,2,7,4,1,3,8,9};
bubble2(a);
}
public static void bubble(int[] a){
for (int j = 0; j < a.length - 1; j++) {
// 一轮冒泡
boolean swapped=false;//默认没有交换
// 优化二减少冒泡次数判断是否交换
// 优化一减少比较次数 -j
for (int i = 0; i < a.length - 1 - j; i++) {
System.out.println("比较次数"+(i+1));
if (a[i]>a[i+1]){
swap(a,i,i+1);
swapped=true;
}
}
System.out.println("第"+(j+1)+"轮冒泡"+ Arrays.toString(a));
if (!swapped) {
break;
}
}
}
public static void bubble2(int[] a){
int n=a.length-1;
while (true){
int last=0;//记录最后一次交换的位置
for (int i=0;i<n;i++){
System.out.println("比较次数"+(i+1));
if (a[i]>a[i+1]){
swap(a,i,i+1);
last=i;
}
}
n=last;
System.out.println("第轮冒泡"+ Arrays.toString(a));
if (n==0){
break;
}
}
}
public static void swap(int[] a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
选择排序
将数组分为两个子集排序和未排序的每一轮从未排序的子集中选出最小的元素放入排序子集重复以上步骤直到整个数组有序循环查找最小元素索引位置 交换
package com.huhu.sort;
import java.util.Arrays;
//理论上的选择排序法
public class SelectSort2 {
public static void main(String[] args) {
int[] arr = {101, 34, 119, 60};
System.out.println("排序前的数组");
System.out.println(Arrays.toString(arr));
selectSort(arr);
}
private static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// i代表每轮选择最小元素要交换到的目标索引
int s=i; //最小元素的索引
for (int j = s + 1; j < arr.length; j++) {
if (a[s] > arr[j]) {
s=j;
}
}
if (s != i) {
swap(a,s,i);
}
System.out.println("第" + (i + 1) + "轮排序后数组");
System.out.println(Arrays.toString(arr));
}
}
public static void swap(int[] a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
选择排序与冒泡排序比较
- 二者平均时间复杂度都是O(n2)
- 选择排序一般要快于冒泡因为其交换次数少
- 但如果集合有序度高冒泡优选O(n)
- 冒泡稳定选择不稳定
插入排序
将数组分为两个区域排序和未排序的每一轮从未排序的区域中取出第一个元素插入到排序区域重复以上步骤直到整个数组有序
package com.huhu.sort;
import java.util.Arrays;
public class InsertSort2 {
public static void main(String[] args) {
int[] a = {9,3,7,2,5,8,1,4};
insert(a);
}
private static void insert(int[] a) {
// i代表待插入元素的索引
for (int i = 1; i < a.length; i++) {
int t = a[i];//t代表待插入元素的值
int j = i - 1;//代表已排序数组的索引
while (j >= 0) {
if (t < a[j]) {
a[j + 1] = a[j];
} else {
break;
}
j--;
}
a[j + 1] = t;
System.out.println(Arrays.toString(a));
}
}
}
插入排序与选择排序比较
- 二者平均时间复杂度都是O(n2)
- 大部分情况下插入优于选择
- 有序集合插入时间复杂度O(n)
- 插入属于稳定排序算法而选择属于不稳定
快速排序
时间复杂度O(nlogn) 最坏O(n) 使用于数据量大 不稳定排序
单边快排
package com.huhu.sort;
import java.util.Arrays;
public class QuickSort1 {
public static void main(String[] args) {
int[] a={5,3,7,2,9,8,1,4};
quick(a,0,a.length-1);
}
public static void quick(int[] a,int l,int h){
if (l>=h){
return;
}
int p=partition(a,l,h);
quick(a,l,p-1);
quick(a,p+1,h);
}
public static int partition(int[] a,int l,int h){
int pv=a[h];//最右为基准元素
int i=l;
for (int j = l; j < h; j++) {
if (a[j]<pv){//比基准小就交换i j元素
if (i!=j){
swap(a,i,j);
}
i++;
}
}
if (i!=h){
swap(a,h,i);
}
System.out.println(Arrays.toString(a)+" i="+i);
return i;//返回值代表基准点元素的正确索引
}
public static void swap(int[] a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
双边快排从右往左找小的 从左往右找大的
package com.huhu.sort;
import java.util.Arrays;
public class QuickSort1 {
public static void main(String[] args) {
int[] a={5,3,7,2,9,8,1,4};
quick(a,0,a.length-1);
}
public static void quick(int[] a,int l,int h){
if (l>=h){
return;
}
int p=partition(a,l,h);
quick(a,l,p-1);
quick(a,p+1,h);
}
public static int partition(int[] a,int l,int h){
int pv=a[l];
int i=l;
int j=h;
while (i<j){
while (i<j&&a[j]>pv){
j--;
}
while (i<j&&a[i]<=pv){//加上等于保证基准元素不会被交换
i++;
}
swap(a,i,j);
}
swap(a,l,j);
System.out.println(Arrays.toString(a)+" j="+j);
return j;//返回值代表基准点元素的正确索引
}
public static void swap(int[] a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}