时间复杂度、空间复杂度、对数器和二分法

1、认识对数器

1.1 基本概念

所谓的对数器，就是当我们编写好一个算法后，我们可以通过对数器生成大量的随机测试样本，并将这些样本用于验证我们编写的算法是否存在问题，可以把对数器简单的理解为一个“自动化测试工具”。

1.2 核心步骤

那么，我们要如何去创建一个对数器呢，核心步骤如下：

• 准备好待测试算法a，也就是我们希望验证是否存在问题的算法；
• 准备一个基准算法b，它和我们需要测试的算法功能一样，区别在于基准算法可以确保自身是没有问题的，它可能是基于暴力解法或者标准库函数来实现的；
• 准备一个随机数生成器，它可以源源不断生成大量测试样本，比如生成随机长度、随机值的数组；
• 准备一个结果比对器，用于比对算法a和b输出的结果是否一致；
• 通过随机数生成器生成大量的随机样本放在算法a和b上执行，再用结果比对器看结果是否一致；
• 将导致算法a和b输出结果不一致的样本打印输出，我们再根据这一样本进行bug修复；

2、选择排序

2.1 基本概念

选择排序就是每次从待排序区间中找到最小（最大）的那个元素，放到已排序区间的末尾，初始时已排序区间是空的，而待排序区间是整个数组，具体步骤如下：

• 从待排序区间内找出最小（最大）的那个元素X；
• 将元素X和待排序区间第一位元素交换位置；
• 已排序区间右边界往右移动一个位置，待排序区间左边界往右移动一个位置；
• 重复上述步骤，直到全部排好序；

2.2 代码实现

public class Code03_SelectSort{
    public static void main(String[] args) {
        int testTimes = 50000;
        int maxLen = 20;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i=0;i<testTimes;i++){
            int[] arr = randomArray(maxLen,maxValue);
            int[] copy1 = Arrays.copyOf(arr, arr.length);
            int[] copy2 = Arrays.copyOf(arr, arr.length);
            selectSort(copy1);
            bm(copy2);
            if (!rc(copy1,copy2)){
                printArray(arr);
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 打印问题样本
     * @param arr
     */
    public static void printArray(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void selectSort(int[] arr){
        //先定边界
        if (arr == null || arr.length < 2){
            return;
        }
        int N = arr.length;
        for (int i=0;i<N;i++){
            int minValueIndex = i;
            for (int j=i+1;j<N;j++){
                minValueIndex = arr[minValueIndex] < arr[j] ? minValueIndex : j;
            }
            swap(arr,i,minValueIndex);
        }
    }

    /**
     * 交换位置
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 基准方法
     * @param arr
     */
    public static void bm(int[] arr){
        Arrays.sort(arr);
    }

    /**
     * 结果比对器
     * @param arr1
     * @param arr2
     * @return
     */
    public static boolean rc(int[] arr1,int[] arr2){
        if (arr1 == null || arr2 == null){
            return false;
        }
        if (arr1.length != arr2.length){
            return false;
        }
        for (int i =0;i<arr1.length;i++){
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    /**
     * 随机生成器
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random() * maxValue) - (int)(Math.random() * maxValue);
        }
        return arr;
    }
}

2.3 性能分析

• 时间复杂度：因为每一轮都需要对所有待排序区间的元素遍历一次，所以它的时间复杂度为O(N^2)；
• 空间复杂度：只用了有限个临时变量，空间复杂度为O(1)；
• 不稳定性：该算法存在“跳跃式交换”，相等元素原本的相对位置在经过排序后可能会变动，比如说：2 2 1，前面的2会跑到后面的2的后面去，所以这是一种不稳定的算法；

3、冒泡排序

3.1 基本概念

冒泡排序就是在待排序区间中从左往右两两比较，较大的那个就往右移动，直到将待排序区间所有元素都遍历一遍，此时处于待排序区间最右边的元素就是待排序区间最大的那个。初始时待排序区间为整个数组，已排序区间为空。具体步骤如下：

• 比较arr[0]和arr[1]的大小，如果arr[0]>arr[1]，交换两个元素的位置，往后走；
• 比较arr[1]和arr[2]的大小，如果arr[1]>arr[2]，交换两个元素的位置，往后走；
• 。。。
• 待排序区间元素全部遍历比较交换完毕，此时待排序区间最末端的元素为最大的那个元素；
• 待排序区间最右端往左移动一个位置，已排序区间最左端往左移动一个位置；
• 重复上述步骤；

3.2 代码实现

public class Code04_BubbleSort {
    public static void main(String[] args) {
        int testTimes = 50000;
        int maxLen = 20;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i=0;i<testTimes;i++){
            int[] arr = randomArray(maxLen, maxValue);
            int[] copy1 = Arrays.copyOf(arr, arr.length);
            int[] copy2 = Arrays.copyOf(arr, arr.length);
            bubbleSort(copy1);
            bm(copy2);
            if (!rc(copy1,copy2)){
                printArray(arr);
            }
        }
        System.out.println("测试结束");
    }

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

    /**
     * 打印问题样本
     * @param arr
     */
    public static void printArray(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    /**
     * 交换位置
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 基准方法
     * @param arr
     */
    public static void bm(int[] arr){
        Arrays.sort(arr);
    }

    /**
     * 结果比对器
     * @param arr1
     * @param arr2
     * @return
     */
    public static boolean rc(int[] arr1,int[] arr2){
        if (arr1 == null || arr2 == null){
            return false;
        }
        if (arr1.length != arr2.length){
            return false;
        }
        for (int i =0;i<arr1.length;i++){
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    /**
     * 随机生成器
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random() * maxValue) - (int)(Math.random() * maxValue);
        }
        return arr;
    }
}

3.3 算法优化

因为冒泡排序不管当前数组是有序的还是无序的，都会无脑的一轮一轮的遍历比较所有元素，为了提升算法的性能，我们可以设置标记位记录本轮遍历是否发生交换，如果没有，说明数组已经有序了，可以直接退出排序。

public static void bubbleSort(int[] arr){
    if (arr == null || arr.length < 2){
        return;
    }
    int N = arr.length;
    for (int end=N-1;end>=0;end--){
        //设置flag标志位，用于记录本轮是否发生过交换
        boolean flag = false;
        for (int second=1;second<=end;second++){
            if (arr[second-1] > arr[second]){
                //发生交换，设置标记位为true
                flag = true;
                swap(arr,second-1,second);
            }
        }
        if (!flag){
            //如果没发生过交换，表明已经有序，直接break
            break;
        }
    }
}

3.4 性能分析

• 时间复杂度：如果加了优化的话，最好时间复杂度为O(N)，也就是数组有序的情况；最差时间复杂度是O(N^2)，总比较次数为N(N-1)/2；
• 空间复杂度：只使用了有限个变量，空间复杂度为O(1)；
• 稳定性：冒泡排序具有稳定性，因为只有当arr[i-1]>arr[i]时，才会发生交换；

4、插入排序

4.1 基本概念

初始时，已排序区间为左边第一个元素，待排序区间为剩下所有的元素，插入排序就是每次从待排序区间拿到第一个元素，然后将它通过比较交换的方式插入到已排序区间对应的位置。具体流程如下：

• 比较已排序区间最后一个元素x和待排序区间第一个元素y的大小；
  • 如果x>y，交换二者的位置；
  • 如果x<=y，不必交换，已经有序，已排序区间往右扩展一个位置，进入下一轮；
• 继续往前比较y和其它已排序区间元素的大小，直到全部比较完毕或者碰到<=y的即可停止，已排序区间往右扩展一个位置，进入下一轮；
• 重复上述步骤。。。

4.2 代码实现

public class Code05_InsertSort {
    public static void main(String[] args) {
        int testTimes = 50000;
        int maxLen = 20;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i=0;i<testTimes;i++){
            int[] arr = randomArray(maxLen, maxValue);
            int[] copy1 = Arrays.copyOf(arr, arr.length);
            int[] copy2 = Arrays.copyOf(arr, arr.length);
            insertSort(copy1);
            bm(copy2);
            if (!rc(copy1,copy2)){
                printArray(arr);
            }
        }
        System.out.println("测试结束");
    }

    public static void insertSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        int N = arr.length;
        for (int end = 1;end<N;end++){
            int curIndex = end;
            while ((curIndex-1 >= 0) && (arr[curIndex-1] > arr[curIndex])){
                swap(arr,curIndex-1,curIndex);
                curIndex--;
            }
        }
    }

    /**
     * 打印问题样本
     * @param arr
     */
    public static void printArray(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    /**
     * 交换位置
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 基准方法
     * @param arr
     */
    public static void bm(int[] arr){
        Arrays.sort(arr);
    }

    /**
     * 结果比对器
     * @param arr1
     * @param arr2
     * @return
     */
    public static boolean rc(int[] arr1,int[] arr2){
        if (arr1 == null || arr2 == null){
            return false;
        }
        if (arr1.length != arr2.length){
            return false;
        }
        for (int i =0;i<arr1.length;i++){
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    /**
     * 随机生成器
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        for (int i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random() * maxValue) - (int)(Math.random() * maxValue);
        }
        return arr;
    }
}

4.3 性能分析

• 时间复杂度：最好时间复杂度为O(N)，也就是数组有序的时候，每一轮只需要进行一次比较即可；最坏时间复杂度是O(N^2)，每一轮都需要对已排序区间所有元素进行比较和交换；
• 空间复杂度：只用了有限个临时变量，空间复杂度为O(1)；
• 稳定性：插入排序相等的两个元素排序后相对位置不会改变，具有稳定性；

5、二分法

5.1 基本概念

二分法就是采用“每次留一半，砍一半”的策略来帮助我们快速逼近目标的查找方法，我的听的比较多的就是二分查找法（Binary Search），在有序的数组中，每次将中间元素和目标值进行比对，不一样的话就砍掉一半继续找，具体步骤如下：

• 选出当前查找区间的中间元素arr[mid]；
• 将中间元素arr[mid]和目标值num进行比对
  • 如果arr[mid]=num，查找完毕；
  • 如果arr[mid]>num，往arr[mid]的左半部分查找；
  • 如果arr[mid]<num，往arr[mid]的右半部分查找；
• 重复上述步骤，直到找到目标元素或者查找失败；

相较于从前往后一个个遍历查找，二分法由于采用了“每次砍一半”的策略，它的查找效率产生了极大的提升，时间复杂度从前者的O(N)提升到了O(logN)级别。

5.2 案例演示

5.2.1 第一题

传统的二分查找，从有序数组arr中查找num，查找成功返回true，查找失败返回false；

public class Code06_BinarySearch {
    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue=100;
        int testTimes = 50000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int target = (int)(Math.random()*maxValue) - (int)(Math.random()*maxValue);
            if (!rc(binarySearch(arr,target),bm(arr,target))){
                printArray(arr);
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 二分查找
     * @param arr
     * @param target
     * @return
     */
    public static boolean binarySearch(int[] arr, int target) {
        if (arr ==null || arr.length == 0){
            return false;
        }
        int L = 0;
        int R = arr.length-1;
        int mid;
        while (L<=R){
            mid = (L+R)/2;
            if (arr[mid] == target){
                return true;
            }else if (arr[mid] < target){
                L = mid+1;
            }else {
                R = mid-1;
            }
        }
        return false;
    }

    /**
     * 基准方法
     * @param arr
     * @param target
     * @return
     */
    public static boolean bm(int[] arr, int target){
        for (int i : arr) {
            if (i == target){
                return true;
            }
        }
        return false;
    }

    /**
     * 结果比对器
     * @param res1
     * @param res2
     * @return
     */
    public static boolean rc(boolean res1,boolean res2){
        if (res1 == res2){
            return true;
        }
        return false;
    }

    /**
     * 随机生成器
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random()*maxLen) + 1;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++){
            arr[i] = (int)(Math.random()*maxValue) - (int)(Math.random()*maxValue);
        }
        //先排序再返回
        Arrays.sort(arr);
        return arr;
    }

    /**
     * 打印有问题的样本
     * @param arr
     */
    public static void printArray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

5.2.2 第二题

在一个有序数组中找出>=num的最左的位置，num是一个给定的数

public class Code07_BSMostLeft {
    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue=100;
        int testTimes = 50000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int target = (int)(Math.random()*maxValue) - (int)(Math.random()*maxValue);
            if (!rc(mostLeft(arr,target),bm(arr,target))){
                printArray(arr);
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 从一个有序数组中找到>=num最左的位置
     * @param arr
     * @param num
     * @return
     */
    public static int mostLeft(int[] arr,int num){
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int ans = -1;
        int L = 0;
        int R = arr.length-1;
        int mid;
        while (L<=R){
            mid = L + ((R-L) >> 1);//等价于mid = (L+R)/2,但是这样写可能会超出整型取值范围
            if (arr[mid] >= num){
                ans = mid;
                R = mid-1;
            }else {
                L = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 基准方法
     * @param arr
     * @param num
     * @return
     */
    public static int bm(int[] arr,int num){
        if (arr == null || arr.length == 0) {
            return -1;
        }
        for (int i=0;i<arr.length;i++){
            if (arr[i] >= num){
                return i;
            }
        }
        return -1;
    }

    /**
     * 结果比对器
     * @param res1
     * @param res2
     * @return
     */
    public static boolean rc(int res1,int res2){
        return res1 == res2;
    }

    /**
     * 随机生成器
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random()*maxLen) + 1;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++){
            arr[i] = (int)(Math.random()*maxValue) - (int)(Math.random()*maxValue);
        }
        //先排序再返回
        Arrays.sort(arr);
        return arr;
    }

    /**
     * 打印有问题的样本
     * @param arr
     */
    public static void printArray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

5.2.3 第三题

局部最小值问题：给定一个无序数组，其内部所有元素都满足相邻元素之间不相等，我们需要从这个数组中随便找一个局部最小值出来，局部最小值满足如下条件：

• arr[0] < arr[1]：0位置就是局部最小值；
• arr[N-1]<arr[N-2]：N-1位置就是局部最小值；
• arr[i-1]>arr[i]<arr[i+1]：i位置就是局部最小值；

public class Code08_LocalMin {
    public static void main(String[] args) {
        int maxLen = 10;
        int maxValue = 100;
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i=0;i<testTimes;i++){
            int[] arr = randomArray(maxLen, maxValue);
            int index = localMinIndex(arr);
            if (!check(arr,index)){
                printArray(arr);
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 返回局部最小值的下标
     * @param arr
     * @return
     */
    public static int localMinIndex(int[] arr){
        if (arr == null || arr.length == 0){
            return -1;
        }
        if (arr.length == 1){
            return 0;
        }
        if(arr[0] < arr[1]){
            return 0;
        }
        int N = arr.length;
        if (arr[N-1] < arr[N-2]){
            return N-1;
        }
        int L = 0;
        int R = N-1;
        while (L < R-1){//这里可以确保至少有三个数，要不然下面的mid+1和mid-1可能会越界
            int mid = L + ((R-L)>>1);
            if (arr[mid-1] > arr[mid] && arr[mid] < arr[mid+1]){
                return mid;
            }else {
                //1.arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1]
                //2.arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1]
                //3.arr[mid-1] > arr[mid] && arr[mid] > arr[mid+1]
                if (arr[mid-1] < arr[mid]){
                    //最左边的两个元素是递减的，从mid-1到mid是递增的，中间一定存在局部最小值
                    R = mid-1;
                }else {
                    //最右边的两个元素是递增的，从mid-1到mid是递减的，中间一定存在局部最小值
                    L = mid+1;
                }
            }
        }
        /**
         * 5 4 7 6 9
         * 5 4 3 9
         * 5 4 6 7 9 10 12
         * 走到这里有两种情况：
         * 1.L == R,也就是只有一个数，那么这个数就是局部最小值
         * 2.L+1 == R,也就是两个数，哪个更小哪个就是局部最小值
         * 疑问：要是arr[L-1] < arr[L] < arr[R]的话，那么L位置怎么会是局部最小值呢？
         * 解答：如果真的存在L-1这个位置，并且arr[L-1]还小于arr[L]，那么必然会往左半边走，而不会往右半边走(L..R这半边)，
         * 因为上面的循环就是为了不断往“山谷”、“低点”走.
         *
         */
        return arr[L] < arr[R] ? L : R;
    }

    /**
     * 随机生成器
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen,int maxValue){
        int len = (int)(Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        arr[0] = (int)(Math.random()*maxValue) - (int)(Math.random()*maxValue);
        for (int i = 1; i < len; i++){
            do{
                arr[i] = (int)(Math.random()*maxValue) - (int)(Math.random()*maxValue);
            }while (arr[i-1] == arr[i]);
        }
        return arr;
    }

    /**
     * 用于检查返回的局部最小值下标是否正确
     * @param arr
     * @param index
     * @return
     */
    public static boolean check(int[] arr,int index){
        if (arr == null || arr.length == 0){
            return index == -1;
        }
        int left = index - 1;
        int right = index + 1;
        boolean leftBigger = left >= 0 ? arr[left] > arr[index] : true;
        boolean rightBigger = right < arr.length ? arr[right] > arr[index] : true;
        return leftBigger && rightBigger;
    }

    /**
     * 输出错误样本
     * @param arr
     */
    public static void printArray(int[] arr){
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}