[数据结构与算法]数据结构与算法（1）

数据结构与算法（1）

一、简单排序算法

1、数字之间的运算符运算

??在Java中二进制数是按照补码的方式存在的。对于正数：原码，补码，反码相同。对于负数：反码是原码除符号位外取反，补码是反码＋1。

（1）与（&）运算符

两个位都为1，则为1，否则为0

public static void positiveAnd(){
    //正数的原码、反码、补码都一样
    //2的二进制码为: 00000000 00000000 00000000 00000010
    int a = 2;
    //6的二进制码为: 00000000 00000000 00000000 00000110
    int b = 6;
    //结果: 00000000 00000000 00000000 00000010
    System.out.println(a & b);
    //结果为:2

}

public static void negativeAnd(){
    //原码取反是反码，反码+1是补码
    //-2的二进制原码: 10000000 00000000 00000000 00000010
    //-2的二进制反码: 11111111 11111111 11111111 11111101
    //-2的二进制补码: 11111111 11111111 11111111 11111110
    int a = -2;
    ///6的二进制码为: 00000000 00000000 00000000 00000110
    int b = 6;
    //-2的二进制补码: 11111111 11111111 11111111 11111110
    ///6的二进制码为: 00000000 00000000 00000000 00000110
    //运算后结果: 00000000 00000000 00000000 00000110
    System.out.println(a & b);
    //结果为：6
}

（2）或（|）运算符

两个数有一个数为1，则为1，否则为0

public static void positiveOr(){
    //正数的原码、反码、补码都一样
    //2的二进制码为: 00000000 00000000 00000000 00000010
    int a = 2;
    //6的二进制码为: 00000000 00000000 00000000 00000110
    int b = 6;
    //结果: 00000000 00000000 00000000 00000110
    System.out.println(a | b);
    //结果为:6

}

public static void negativeOr(){
    //原码取反是反码，反码+1是补码
    //-2的二进制原码: 10000000 00000000 00000000 00000010
    //-2的二进制反码: 11111111 11111111 11111111 11111101
    //-2的二进制补码: 11111111 11111111 11111111 11111110
    int a = -2;
    ///6的二进制码为: 00000000 00000000 00000000 00000110
    int b = 6;
    //-2的二进制补码: 11111111 11111111 11111111 11111110
    ///6的二进制码为: 00000000 00000000 00000000 00000110
    //运算后结果: 11111111 11111111 11111111 11111110
    System.out.println(a | b);
    //结果为：-2
}

（3）非（~）运算符

正数：取反为补码，将补码减1转换成反码，反码取反为原码
负数：从原码换算成补码，然后在取反

public static void positiveNot(){
    //正数的原码、反码、补码都一样
    //2的二进制码为: 00000000 00000000 00000000 00000010
    int a = 2;
    //取反后结果(补码): 11111111 11111111 11111111 11111101
    //二进制反码: 11111111 11111111 11111111 11111100
    //二进制原码: 10000000 00000000 00000000 00000011
    //System.out.println(~a);
    //结果为:-3

}

public static void negativeNot(){
    //-2的二进制原码: 10000000 00000000 00000000 00000010
    //二进制反码: 11111111 11111111 11111111 11111101
    //二进制补码: 11111111 11111111 11111111 11111110
    int a = -2;
    //(补码)取反后结果: 00000000 00000000 00000000 00000001
    System.out.println(~a);
    //结果为：1
}

（4）异或（^）运算符

相同为0，不同为1

异或运算也可以理解为无进位相加：

public static void positiveXOR(){
    //相同为0，不同为1
    //2的二进制码为: 00000000 00000000 00000000 00000010
    int a = 2;
    //6的二进制码为: 00000000 00000000 00000000 00000110
    int b = 6;
    //结果(补码): 00000000 00000000 00000000 00000101
    //二进制反码: 00000000 00000000 00000000 00000100
    //二进制原码: 00000000 00000000 00000000 00000100
    System.out.println(a ^ b);
    //结果为:4

}

public static void negativeXOR(){
    //相同为0，不同为1
    //-2的二进制原码: 10000000 00000000 00000000 00000010
    //-2的二进制反码: 11111111 11111111 11111111 11111101
    //-2的二进制补码: 11111111 11111111 11111111 11111110
    int a = -2;
    ///6的二进制码为: 00000000 00000000 00000000 00000110
    int b = 6;
    //结果(补码): 11111111 11111111 11111111 11111000
    //二进制反码: 11111111 11111111 11111111 11110111
    //二进制原码: 10000000 00000000 00000000 00001000
    System.out.println(a ^ b);
    //结果为:-8
}

2、认识时间复杂度

??时间复杂度是常数时间的操作，一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

??时间复杂度为一个算法流程中，常数操作数量的一个指标。常用0(读作big 0)来表示。具体来说，先要对一个算法流程非常熟悉，然后去写出这个算法流程中，发生了多少常数操作，进而总结出常数操作数量的表达式。在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为f(N)，那么时间复杂度为0(f(N)）。

??评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同数据样本下的实际运行时间，也就是“常数项时间”。

案例：

对于下面的程序，只有在确认执行时间后才能确定他的流程好坏。

public class Test01 {

    public static void process1(){
        long n=System.currentTimeMillis();
        int N=10;
        int a=0;
        for (int i = 0; i < n; i++) {
            a=2+5;
            a=4*7;
            a=6*8;
        }
        long m=System.currentTimeMillis();
        System.out.print("所需时间为：");
        System.out.println(m-n);
    }

    public static void process2(){
        long n=System.currentTimeMillis();
        int N=10;
        int a=0;
        for (int i = 0; i < N; i++) {
            a=3|6;
            a=3&4;
            a=4^785;
        }
        long m=System.currentTimeMillis();
        System.out.print("所需时间为：");
        System.out.println(m-n);
    }

    public static void main(String[] args) {
        Test01.process1();
        System.out.println("-----------");
        Test01.process2();
    }
}

对于时间复杂度：有三种指标

• O(……)：最差情况下的时间复杂度
• θ(……)：平均情况下的时间复杂度
• Ω(……)：最优情况下的时间复杂度

3、简单排序算法

（1）选择排序

// 选择排序 时间复杂度O(n*n) 空间复杂度O(1)
public class SelectionSort {

    public static void selectionSort(int[] arr) {
        if (arr == null | arr.length <= 1) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[minIndex] < arr[j] ? minIndex : j;
            }
            swap(i, arr, minIndex);
        }

    }

    public static void swap(int m, int[] arr, int n) {
        int tmp = arr[m];
        arr[m] = arr[n];
        arr[n] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {12, 1, 23, 3, 5, 4, 7};
        selectionSort(arr);
        System.out.println("数组快速排序后："+Arrays.toString(arr));
    }
}

（2）冒泡排序

// 冒泡排序 时间复杂度O(n*n) 空间复杂度O(1)
public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        if (arr == null | arr.length <= 1) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(j, j + 1, arr);
                }
            }
        }
    }

    // 两数交换
    public static void swap(int m, int n, int[] arr) {
        arr[m] = arr[m] ^ arr[n];
        arr[n] = arr[m] ^ arr[n];
        arr[m] = arr[m] ^ arr[n];
    }

    public static void main(String[] args) {
        int[] arr = {12, 1, 23, 3, 5, 4, 7};
        bubbleSort(arr);
        System.out.println("数组冒泡排序后：" + Arrays.toString(arr));
    }
}

（3）异或（^）运算性质

1. N ^ 0=N，N ^ N=0;
2. 交换律和结合律 a ^ b=b ^ a
   a ^ b ^ c=a ^ (b^c)

根据这些性质可以通过异或运算实现两数交换

实现的前提是arr[m]的位置和arr[n]位置不同，否则全部为0

public static void swap(int m, int n, int[] arr) {
    arr[m] = arr[m] ^ arr[n];
    arr[n] = arr[m] ^ arr[n];
    arr[m] = arr[m] ^ arr[n];
}

针对于常见的两数交换的优势在于节省了一个变量空间。

（4）异或（^）运算案例

public class Code03_Xor {

    /**
     * 异或问题案例1
     * 问题描述：传入一个数组，其中一个数组元素出现了奇数次，其他数组元素出现了偶数次
     * 需求描述：找出该数组元素
     *
     * @param arr 数组
     */
    public static void xor01(int[] arr) {
        if (arr == null | arr.length <= 2) {
            return;
        }
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        System.out.println("该数为：" + eor);
    }

    /**
     * 异或问题案例2
     * 问题描述：传入一个数组，其中两个数组元素出现了奇数次，其他数组元素出现了偶数次
     * 需求描述：找出这两个数组元素
     *
     * @param arr 数组
     */
    public static void xor02(int[] arr) {
        if (arr == null | arr.length <= 2) {
            return;
        }
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // eor = a ^ b;
        // eor != 0
        // eor 必然有一个位置上有1
        int rightOne = eor & (~eor + 1);  // 提取出最右的1
        int onlyOne = 0;
        for (int i = 0; i < arr.length; i++) {
            // 也可判断是否等于rightOne（相与不是为0就是为rightOne）
            if ((arr[i] & rightOne) == 0) {
                onlyOne ^= arr[i];
            }
        }
        System.out.println("其中一个数为：" + onlyOne);
        System.out.println("另一个数为：" + (eor ^ onlyOne));


    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 2};
        int[] arr2 = {7, 4, 4, 3};
        xor01(arr1);
        xor02(arr2);
    }
}

对于：int rightOne = eor & (~eor + 1); // 提取出eor最右的1提取出最右侧1的解释

eor:
1010 1111  原码
1101 0000   反码
1101 0001   补码

~eor:
0010 1110  补码取反仍然为补码
由于是正数，则原码依然为
0010 1110

~eor+1:
0010 1111 原码

eor&(~eor+1)补码相与
1101 0001 &
0010 1111
为0000 0001（正数）

最终结果为：
原码为0000 0001
提取出最右边的1

（5）插入排序

// 插入排序 时间复杂度按照最差情况估计算法表现为O(n*n),空间复杂度为O(1)
public class Code4_InsertionSort {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 0~0有序
        // 0~1有序
        for (int i = 1; i < arr.length; i++) {  // 0~i范围有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(j, j + 1, arr);
            }
        }
    }

    // 两数交换
    public static void swap(int m, int n, int[] arr) {
        arr[m] = arr[m] ^ arr[n];
        arr[n] = arr[m] ^ arr[n];
        arr[m] = arr[m] ^ arr[n];
    }

    public static void main(String[] args) {
        int[] arr = {12, 1, 23, 3, 5, 4, 7};
        insertionSort(arr);
        System.out.println("数组插入排序后：" + Arrays.toString(arr));
    }
}

（6）二分查找

常见运用场景：

• 在一个有序数组中，查找一个数组中是否存在某个数

• 在一个有序数组中，查找>=某个数的最左侧位置

• 在一个无序数组中，相邻数一定不相等，找到局部最小的数

（7）对数器的概念和使用

1、有一个你想要测的方法a

2、实现复杂度不好但是容易实现的方法b

3、实现一个随机样本产生器

4、把方法a和方法b跑相同的随机样本，看看得到的结果是否一样。

5、如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b

6、当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

举例

// 插入排序 时间复杂度按照最差情况估计算法表现为O(n*n),空间复杂度为O(1)
public class Code4_InsertionSort {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 0~0有序
        // 0~1有序
        for (int i = 1; i < arr.length; i++) {  // 0~i范围有序
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(j, j + 1, arr);
            }
        }
    }

    // 两数交换
    public static void swap(int m, int n, int[] arr) {
        arr[m] = arr[m] ^ arr[n];
        arr[n] = arr[m] ^ arr[n];
        arr[m] = arr[m] ^ arr[n];
    }

    // for test
    // 工具类排序
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    // 生成随机数组
    public static int[] generateRandomArray(int maxSize, int maxValue) {

        // Math.random() -> [0,1)所有的小数，等概率返回一个
        // Math.random()*N -> [0,N)所有的小数，等概率返回一个
        // (int)(Math.random()*N) -> [0,N-1] 所有的整数，等概率返回一个

        int[] arr = new int[(int) (Math.random() * (maxSize + 1))];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    // 复制数组
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] copyArr = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            copyArr[i] = arr[i];
        }
        return copyArr;
    }

    // for test
    // 判断arr1和arr2的排序后的值和数组长度是不是一样
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    // 输出数组
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int testTime = 5000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            insertionSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                // 打印arr1
                // 打印arr2
                succeed = false;
                break;
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");

            int[] arr = generateRandomArray(maxSize, maxValue);
            printArray(arr);
            insertionSort(arr);
            printArray(arr);
        }
    }
}

??可以看到generateRandomArray方法生成了数值量很大的随机数组，测试testTime次，确定方法insertionSort是否正确。