算法+二分查找+冒泡排序+位运算【Interview】

目录

1什么是算法？

1.1什么是位运算？

2什么是算法复杂度？

3常见的算法了解几个？手写一个冒泡，手写一个二分查找？

1什么是算法？

算法可以理解为Java中一个方法的所有步骤的集合。

1.1什么是位运算？

位运算？

计算机中的数在内存中都是以二进制形式进行存储的

a<<2 = a*2^2【2次方】==左移

a>>2 = a/2^2【2次方】==右移

2什么是算法复杂度？

算法复杂度分为时间复杂度和空间复杂度

时间复杂度：衡量算法执行时间的长短

空间复杂度：衡量算法所需的存储空间的大小【缓存以空间换时间】

时间复杂度是用来度量算法执行的时间的长短，一个算法花费的时间与算法中语句的执行次数成正比例

通常我们用Ｏ(f(n))渐进时间复杂度来衡量，比如说

JAVA冒泡排序和二分查找的实现

pdf 0星 超过10%的资源 63KB

下载

eg：如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

• 要在 hash 表中找到一个元素就是 O(1)

• 要在无序数组中找到一个元素就是 O(n)【最小是O（1）最大是O（n）】

• 访问数组的第 n 个元素是 O(1)【直接通过下标进行获取】

• 二分搜索的时间复杂度最好的情况是 O(1)，最坏情况（平均情况）下 O(log n)

• 访问链表的第 n 个元素是 O(n)【需要执行n次，一个一个进行遍历】

• 一个For循环是O(n)

• 两个For循环嵌套是O(n2次方)

• 三个Foreach嵌套是O(n3次方)

3常见的算法了解几个？手写一个冒泡，手写一个二分查找？

排序算法：

 这些算法可以在菜鸟教程上进行学习。

1.1 冒泡排序 | 菜鸟教程

public class BubbleSortTest {
    public static void main(String[] args) {
        // 创建一个集合对象
        int[] arr = {55,25,33,42,343,4};
        int num = 1 ;
        // 需要执行的次数
        for(int j = 0 ; j < arr.length -1 ; j++){
            // 这个是来判别集合对象中数据是否已经排序好了。就不用执行里面的for循环了，提高执行效率。
            boolean isOk = true;
            // 执行一个这个方法会获取集合中一个最大的值并存储到集合的最后面
            // 【比一次就少进行比较一次，因为最大值已经在最后，不需要再比较了】
            for(int i = 0 ; i < arr.length -1 - j; i++){
                // 前面的值比后面大
                if(arr[i] > arr[i+1]){
                    // 交换位置
                    int temp = arr[i];
                    arr[i] = arr[i+1];
                    arr[i+1] = temp;
                    // 进来了，说明没有排好序
                    isOk = false;
                    System.out.println("发生次"+(num++)+"交换");
                }
            }
            // 直接结束当前方法
            if(isOk)break;
        }
 
        for (int a : arr) {
            System.out.println(a);
        }
    }
}

查找算法

• 顺序查找

• 二分查找

• 插值查找

• 斐波那契查找

• 树表查找

• 分块查找

• 哈希查找

C++实现双向冒泡排序算法

pdf 0星 超过10%的资源 63KB

下载

二分查找【二分查找的前提是要对集合进行排序。】

最低位：0

最高位：数组长度-1

确定中间位：（低位+高位）/2【向下取整】

值如果等于中间位置的值，找到了

值如果大于中间位置的值，最低位要变成中间位+1

值如果小于中间位置的值，最高位就是中间位-1

如果低位大于等于高位了，还没找到，就没有。

二分法是向下取整，计算公式是：mid=low+(high-low)/2;

下图：left指的是低位，right指的是高位。mid指的是中间位

/**
 * 二分查找
 * 二分查找的前提是要对集合进行排序。
 * */
public class BinaryFound {
 
    public static void main(String[] args) {
        List arrs = Arrays.asList(1,3,4,8,33,44,55,6677,333);
        Collections.sort(arrs);
 
        // 最低位和最高位
        int low = 0;
        int high = arrs.size() - 1;
 
        // 需要查询的数字
        int value = 8888;
        // 查找的次数
        int count = 1 ;
 
        // 当低位小于等于高位，就进行二分查找
        while(low <= high){
            System.out.println("查找次数"+(count++));
            // 获取的是下标
            int mid = (low + high ) / 2;
            if(arrs.get(mid) == value) {
                System.out.println("找到啦,位置是"+mid);
                break;
            }
            // 如果值大于中间值，说明在右边
            if(value > arrs.get(mid)){
                low = mid + 1;
            }
            // 如果值小于中间值，说明在左边
            if(value < arrs.get(mid)){
                high = mid - 1;
            }
        }
    }
}