第1节 位运算、算法是什么、简单排序

  • 开发
  • 39

位运算

package class01;
// 位运算
public class Code_Print {
    // 打印二进制方法
    public static void print(int num){
        for (int i = 31; i>=0; i--){
            System.out.print( (num & (1 << i)) == 0 ? "0" : "1" ); // num跟其&完是0这个状态即为0，否则为1
            // 1 << i 1向左移动31为   00000000....01 变为 10000000...0
            // num & (1 << i) &完  11 1   10 0  01 0  00 0
            // 左移的意思的右边用0来补，左移一位的到的数字就是原本的数字*2  2的0次方左移是2的1次方
        }
        System.out.println();
    }

    public static void main(String[] args) {
        /*
        整型是32位
        * */
//        int num = 1;
//        print(num); // 00000000000000000000000000000001
//        int test = 112423;
//        print(test); // 00000000000000011011011100100111
//        print(test<<1); //左移一位 00000000000000110110111001001110
//        print(test<<2); //左移2位 00000000000001101101110010011100
//        print(test<<8); // 00000001101101110010011100000000

//        int a = Integer.MAX_VALUE; // int的正数最大值
//        System.out.println(a); // 打印整型的最大值 2147483647   2的31次方 -1  2的31次方是2147483648
        // 一个整型会留着最高位的1不占。即一个整型在系统中32位不是都用的，留着最高位的1有特殊含义(表示符号，0表示是非负数，1表示负数)，真正表示值的范围是0到30位这个范围，即为2的31次方 -1，
        // 无符号数 是0~2的32次方 -1     0~2的31次方 -1 算上0，一共有2的32次方个数，
        // int 是有符号数，既能表示+ 又能表示-，即他的范围是-2的31次方~2的31次方 -1。  原本是2的32次方 -1，但是有符号，所以一半分给正一半分给负.
//        print(a); // 01111111111111111111111111111111

        /*
        ~ 取反符号，即0反1
        负数都是取反+1得到的
        */
//        print(-1); // 11111111111111111111111111111111,第一位代表负号（符号位不管处理后面的，把后面的所有数取反，即全为0，再+1，就是-1。0000000000000000000000000000001 1
//        int b = Integer.MIN_VALUE; // int的负数最小值
//        System.out.println(b); // -2147483648 -2的31次方
//        print(b);
        //10000000000000000000000000000000,除符号位取反值 01111111111111111111111111111111，再+1，全进位，
        // 变成 10000000000000000000000000000000 2的31次方 2147483648 加上符号就是 -2147483648

        // 总结0的归属再非负区，不在负区，所以正数的最大值是2的31次方 -1 ，负数的最小值是-2的31次方。 先确定符号！！！，取反正常取反就行！！！！


        /*
        * 测试
        * */
//        int a = 1231924;
//        int b = 41255132;
//        print(a); //00000000000100101100110000110100
//        print(b); //00000010011101011000000011011100
//        System.out.println("================");
//        print(a | b); //00000010011101111100110011111100 有1则1
//        print(a & b); //00000000000100001000000000010100 都为1才为1
//        print(a ^ b); //00000010011001110100110011101000 相同为0，不同为1

        /*
        * 右移
        * */
//        int a = Integer.MIN_VALUE;
//        print(a); // 10000000000000000000000000000000
//        print(a >> 1);//  11000000000000000000000000000000,不带符号右移
//        print(a >>> 1);// 01000000000000000000000000000000,带符号右移

        /*
        * 相反数
        * */
//        int c = 5;
//        int d = -c;
//        int d = (~c + 1); // 负号的另一种表达。即~N+1 = N的相反数
//
//        System.out.println(c); // 5
//        System.out.println(d); // -5
//        print(~d); // 11111111111111111111111111111011,除符号位取反00000000000000000000000000000100, +1 00000000000000000000000000000101 -5

//        int c = Integer.MIN_VALUE ; // -2147483648
//        int d = (~c+1);
//        System.out.println(d); // -2147483648
//        print(d); // 10000000000000000000000000000000,取反01111111111111111111111111111111，+1 10000000000000000000000000000000 所以相反数还是-2147483648

        // 0取反是它自己



    }
}

算法

算法

  1. 有具体的问题
  2. 有设计解决这个问题的具体流程
  3. 有评价处理流程的可量化指标

算法的分类

  1. 分类很多
  2. 大体分两类
    1. 明确知道怎么算的流程
    2. 明确知道怎么尝试的流程

  • 求阶乘例子 
    • package class01;

public class Code_SumOfFactorial {
    // f1求阶乘，1*2*3*........N
    public static long f1(int N){
        long ans = 0;
        for (int i = 1; i<=N; i++){
            ans += factorial(i);
        }
        return ans;
    }
    public static long factorial(int N){
        long ans = 1;
        for (int i=1; i<=N; i++){
            ans *= i;
        }
        return ans;
    }

    // f2求阶乘 (N-1)! * N
    public static long f2(int N){
        long ans = 0;
        long cur = 1;
        for (int i = 1; i <= N; i++){
            cur = cur * i;
            ans += cur;
        }
        return ans;
    }

    public static void main(String[] args) {
        int N = 10;
        System.out.println(f1(N)); // 4037913
        System.out.println(f2(N)); // 4037913
    }
}

简单排序

选择排序

  • 0~N-1上选出最小值放到0位置
  • 1~N-1上选出最小值放到1位置
  • 2~N-1上选出最小值放到2位置 …….
  • package class01;

public class Code_SelectionSort {

    public static void selectSort(int[] arr) { // 写选择排序方法
        if (arr == null || arr.length < 2) {   // 边界条件
            return;
        }
        int N = arr.length;
        // 0 ~ n-1
        // 1 ~ n-1
        // 2 ~ n-1
        for (int i = 0; i < N; i++) { // i指定范围
            // 0 ~ n-1
            // 1 ~ n-1
            // 2 ~ n-1
            // .........
            // i ~ n-1
            int minValueIndex = i; // 定义最小值的位置变量
            // 找出最小值的位置
            for (int j = i + 1; j < N; j++) {

                // 最小值比arr[j] 大，取出j的索引，否则索引不变，还是前面的 minValueIndex
                minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
            }
            // i位置的数是最左的数
            swap(arr, i, minValueIndex); // 把i位置和最小值位置上的数交换
        }
    }

    public static void swap(int[] arr, int i, int j) { // 写个交换方法，把i位置的数和j位置的数交换
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void printArray(int[] arr) { // 打印数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        printArray(arr); // 7 1 3 5 1 6 8 1 3 5 7 5 6
        selectSort(arr);
        printArray(arr); // 1 1 1 3 3 5 5 5 6 6 7 7 8
    }


}

 冒泡排序

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  • package class01;

public class Code_BubbleSort {
    public static void swap(int[] arr, int i, int j) { // 交换方法
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {   // 边界条件
            return;
        }
        // 0~n-1
        // 0~n-2
        // 0~n-3
        // 0~end
        int N = arr.length;
        for (int end = N - 1; end >= 0; end--) {
            // 0~end 干事情
            // 0 1  1 2   2 3  3 4  end-1 end  之间的交换
            for (int second = 1; second <= end; second++) { // second 从1到end
                if (arr[second - 1] > arr[second]) {
                    swap(arr, second, second - 1);
                }
            }
            // 或者
//            for (int second = 0; second <= end-1; second++) { // second 从0到end-1
//                if (arr[second] > arr[second+1]) {
//                    swap(arr, second+1, second);
//                }
//            }
        }
    }

    public static void printArray(int[] arr) { // 打印数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        printArray(arr); // 7 1 3 5 1 6 8 1 3 5 7 5 6
        bubbleSort(arr);
        printArray(arr); // 1 1 1 3 3 5 5 5 6 6 7 7 8
    }
}

 插入排序

  • 假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

  • 按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
  • package class01;

public class Code_InsertionSort {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void insertSort1(int[] arr) { // 方法一
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0~0 完成
        // 0~1
        // 0~2
        // 0~3.....
        // 0~n-1 结尾在变
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            int newNumIndex = end; // 新来的数在哪个位置
            while (newNumIndex - 1 >= 0 && arr[newNumIndex - 1] > arr[newNumIndex]) { // 如果数的位置-1大于等于0（意思是左边一定要有数才能继续判断）并且满足左边的数大于右边的数，则需要交换
                swap(arr, newNumIndex - 1, newNumIndex);
                newNumIndex--; // 左移就--
                // 左边没数，或者左边数小于右边的数，它就会跳出循环
            }
        }
    }

    public static void insertSort2(int[] arr) { // 方法二
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int end = 1; end < N; end++) {
            // pre是新数的前一个位置。   新数开始在end位置上
            for (int pre = end - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
                swap(arr, pre, pre + 1);
            }
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4, 8, 2, 4, 26, 7, 9, 34, 23};
        printArray(arr);
        insertSort1(arr);
        printArray(arr);
        insertSort2(arr);
        printArray(arr);
    }
}

阅读全部

相关推荐

  1. 第1节 位运算、算法是什么、简单排序

    2023-12-19 13:30:02       40 阅读

  3. 第二章 - 第1节- 逻辑运算 -课后习题

    2023-12-19 13:30:02       5 阅读

  5. 用PYTHON学算法DAY1--位运算相关

    2023-12-19 13:30:02       34 阅读

  7. leetcode算法-位运算

    2023-12-19 13:30:02       30 阅读

  9. 算法-位运算

    2023-12-19 13:30:02       27 阅读

  10. 位运算算法

    2023-12-19 13:30:02       21 阅读

最近更新

  4. TCP协议是安全的吗?

    2023-12-19 13:30:02       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2023-12-19 13:30:02       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2023-12-19 13:30:02       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2023-12-19 13:30:02       20 阅读

热门阅读

  1. 目标检测里面MAP评测指标的详细介绍

    2023-12-19 13:30:02       39 阅读

  7. 前端面试题（计算机网络）：POST和PUT请求的区别

    2023-12-19 13:30:02       40 阅读

  8. Wireshark高级网络安全分析

    2023-12-19 13:30:02       67 阅读

  13. 【数组Array】力扣-370 区间加法

    2023-12-19 13:30:02       49 阅读

  14. 2023.12.17力扣每日一题

    2023-12-19 13:30:02       45 阅读

  15. openssl生成https

    2023-12-19 13:30:02       44 阅读

  17. 视觉SLAM中的相机分类及用途

    2023-12-19 13:30:02       40 阅读

  18. 【matlab】MATLAB常用内置函数&示例

    2023-12-19 13:30:02       38 阅读

  19. npm ERR! path /Users/apple/.npm/_cacache/index-v5/11/77/cf18d9ab54d565b57fb3

    2023-12-19 13:30:02       42 阅读

  22. conda和pip配置国内镜像源

    2023-12-19 13:30:02       42 阅读

  25. 第79讲： MySQL Binlog二进制日志恢复误删数据的实践指南

    2023-12-19 13:30:02       41 阅读