01 认识复杂度、对数器、二分法

第1节.pptx

1 排序算法

题目1 选择排序

     /**
     * 选择排序
     */
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        /*
        * 0~N-1
        * 1~N-1
        * 2~N-1
        */
        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(arr, i, minIndex);
        }
    }
    /**
     * 交换数组两个下标的数
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

题目2 冒泡排序

     /**
     * 冒泡排序
     *
     * @param arr 数组
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        /*
         * 0~N-1
         * 0~N-2
         * 0~N-3
         * ...
         * 0~1
         * */
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
    /**
     * 交换数组两个下标的数
     * 两个下标不指向同一块内存空间，可使用不增加变量的方式交换
     */
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

题目3 插入排序

    /**
     * 插入排序
     *
     * @param arr 数组
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
        }
    }
    /**
     * 交换数组两个下标的数
     * 两个下标不指向同一块内存空间，可使用不增加变量的方式交换
     */
    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

题目4 希尔排序——改进的插入排序

 public static void shellSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int h = 1;
    while (h <= arr.length / 3) {
        h = 3 * h + 1;
    }
    for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j > gap - 1 && arr[j] < arr[j - gap]; j -= gap) {
                swap(arr, j, j - gap);
            }
        }
    }
}

4 二分法应用

题目1：在一个有序数组中，找某个数是否存在

    /**
     * 有序数组，二分查找一个数是否存在，返回数的下标
     * @param arr 数组
     * @param num 数
     * @return 下标，不存在返回-1
     */
    public static int binarySearch(int[] arr, int num) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] == num) {
                return mid;
            } else if (arr[mid] < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

题目2：在一个有序数组中，找>=某个数最左侧的位置

     /**
     * 在一个有序数组中，找>=某个数最左侧的位置
     *
     * @param arr
     * @param num
     * @return
     */
    public static int binarySearchNearLeft(int[] arr, int num) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int index = -1;
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] >= num) {
                index = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return index;
    }

题目3：局部最小值问题

    /**
     * 局部最小值问题
     *
     * @param arr 随机数组，满足相邻2个数不相等
     * @return 任意一个局部最小值
     */
    public static int binarySearchAwesome(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int index = -1;
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                index = mid;
                break;
            } else if (arr[mid] > arr[mid - 1]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return index;
    }