19常用算法.md

JavaStudy

查找算法

一、二分查找

    private static int binarySearch(ArrayList<Integer> arr,int num) {
        int i = 0;
        int j = arr.size()-1;
        int mid;
        while(i <= j){
            mid = (i+j)/2;
            if(num < arr.get(mid)){
                j = mid - 1;
            }else if(num > arr.get(mid)){
                i = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

二、插值查找

    private static int insertSearch(ArrayList<Integer> arr,int num) {
        int i = 0;
        int j = arr.size()-1;
        int mid;
        while(i <= j){
            //插值查找和对分查找唯一的不同就在于mid的计算方式，这样的计算方式更接近结果
            mid = i + (num - arr.get(i))/(arr.get(j) - arr.get(i))*(j-i);
            if(num < arr.get(mid)){
                j = mid - 1;
            }else if(num > arr.get(mid)){
                i = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

三、斐波那契查找

    private static int insertSearch(ArrayList<Integer> arr,int num) {
        int i = 0;
        int j = arr.size()-1;
        int mid;
        while(i <= j){
            //斐波那契查找：mid = min + 黄金分割点左半边长度-1，本质上也是二分查找的变形
            mid = min + ( j - i ) * 0.618 -1;
            if(num < arr.get(mid)){
                j = mid - 1;
            }else if(num > arr.get(mid)){
                i = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

四、分块查找

在实际开发中，数据不可能完全有序，也不可能完全无序，所以要分块查找


    public static void main(String[] args) { 
        //比如在下面这个数组中
        int[] list = {7,10,13,19,16,20,27,22,30,40,36,43,50,48};
        //可以看做块内无序，块外有序
        //分块的原则1.前一块中的最大数据，小于后一块中所有的数据
        //分块的原则2.快数量一般等于数字的个数开根号，比如16个数字一般分为4块左右
        //核心思路：先确定要查找的元素在哪一块，然后在块内顺序查找
        //         1.对每一个块创建对象
        //         2.创建包含块对象的数组，称为索引表
        //         3.用二分查找找到对应块，再在块中查找数据

        ////代码实现////
        //1.分块：数量：根号下18，所以4个
        //2.创建三个块的对象
        Block b1 = new Block(21,0,5);
        Block b2 = new Block(45,6,11);
        Block b3 = new Block(73,12,17);
        //定义数组用于管理块的对象：
        Block[] blockArr = {b1,b2,b3};

        //定义一个变量，记录需要查找的对象：
        int number = 60;

        //调用方法，传递索引表，数组，元素
        int index = getIndex(blockArr,list,number);
        System.out.println(index);
    }

    private static int getIndex(Block[] blockArr, int[] list, int number) {
        int index = 0;
        while(index < blockArr.length && number > blockArr[index].getMax()){
            index ++;
        }
        if(index >= blockArr.length){
            return -1;
        }
        System.out.println(index);
        int end =  blockArr[index].getEndIndex();
        index = blockArr[index].getStartIndex();
        while(index < list.length && list[index] != number && index < end){
            index++;
        }
        if(index >= list.length){
            return -1;
        }else{
            return index;
        }
    }

排序算法

快速排序

    private static void quickSort(int[] list, int i, int j) {
        int start = i;
        int end = j;
        int temp;
        //递归的出口：
        if(i >= j){
            return;
        }

        //记录基准数：
        int baseNumber = list[i];

        //利用循环找到要交换的数字：
        while(start != end){
            //利用end开始找比基准数小的数字
            while(true){
                if(end <= start || list[end] < baseNumber){
                    break;
                }
                end--;
            }
            //利用start找比基准数大的数字
            while(true){
                if(end <= start || list[start] > baseNumber){
                    break;
                }
                start++;
            }

            //把end和start指向的对象交换
            temp = list[start];
            list[start] = list[end];
            list[end] = temp;
        }
        //当end和start指向同一个数字，那么循环就会结束，此时需要基准数归位
        temp = list[i];
        list[i] = list[end];
        list[end] = temp;
        quickSort(list,i,end - 1);
        quickSort(list,end + 1,j);
    }

插入排序

    private static int[] insertSort(int[] list) {
        int[] result = list.clone();
        int index;
        int temp;
        for (int i = 1; i < result.length; i++) {
            index = i;
            while(index > 0 && result[index] >= result[index -1]){
                temp = result[index -1];
                result[index -1] = result[index];
                result[index] = temp;
                index--;
            }
        }
        return result;
    }

冒泡排序

public void bubbleSortOpt(int[] arr) {

	if(arr == null) {
        throw new NullPoniterException();
    }
    if(arr.length < 2) {
        return;
    }
    int temp = 0;
    for(int i = 0; i < arr.length - 1; i++) {
        for(int j = 0; j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

冒泡排序优化

public static int bubbleSortOpt3(int[] arr) {

    if (arr == null) {
        throw new RuntimeException();
    } else if (arr.length < 2) {
        return 0;
    }

    int temp;
    int count = 0;
    int len = arr.length - 1;
    for (int i = 0; i < len; i++) {
        // 记录最后一次交换位置
        int lastChange = 0;
        for (int j = 0; j < len; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                // 每交换一次更新一次
                lastChange = j;
            }
            count++;
        }
        // 没有发生交换，排序已经完成
        if (lastChange == 0) {
            return count;
        }
        len = lastChange;
    }
    return count;
}

希尔排序

某些情况下直接插入排序的效率极低。比如一个已经有序的升序数组，这时再插入一个比最小值还要小的数，也就意味着被插入的数要和数组所有元素比较一次。我们需要对直接插入排序进行改进。

怎么改进呢？前面提过，插入排序对已经排好序的数组操作时，效率很高。因此我们可以试着先将数组变为一个相对有序的数组，然后再做插入排序。

希尔排序能实现这个目的。希尔排序把序列按下标的一定增量（步长）分组，对每组分别使用插入排序。随着增量（步长）减少，一直到一，算法结束，整个序列变为有序。因此希尔排序又称缩小增量排序。

一般来说，初次取序列的一半为增量，以后每次减半，直到增量为一。

public void shellSort(int[] arr) {
    // gap 为步长，每次减为原来的一半。
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 对每一组都执行直接插入排序
        for (int i = 0 ;i < gap; i++) {
            // 对本组数据执行直接插入排序
            for (int j = i + gap; j < arr.length; j += gap) {
                // 如果 a[j] < a[j-gap]，则寻找 a[j] 位置，并将后面数据的位置都后移
                if (arr[j] < arr[j - gap]) {
                    int k;
                    int temp = arr[j];
                    for (k = j - gap; k >= 0 && arr[k] > temp; k -= gap) {
                        arr[k + gap] = arr[k];
                    }
                    arr[k + gap] = temp;
                }
            }
        }
    }
}

选择排序

public static void selectSort(int[] arr) {
    // 遍历所有的数
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        // 把当前遍历的数和后面所有的数进行比较，并记录下最小的数的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                // 记录最小的数的下标
                minIndex = j;
            }
        }
        // 如果最小的数和当前遍历的下标不一致，则交换
        if (i != minIndex) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

堆排序

/**
 * 转化为大顶堆
 * @param arr 待转化的数组
 * @param size 待调整的区间长度
 * @param index 结点下标
 */
public void maxHeap(int[] arr, int size, int index) {
    // 左子结点
    int leftNode = 2 * index + 1;
    // 右子结点
    int rightNode = 2 * index + 2;
    int max = index;
    // 和两个子结点分别对比，找出最大的结点
    if (leftNode < size && arr[leftNode] > arr[max]) {
        max = leftNode;
    }
    if (rightNode < size && arr[rightNode] > arr[max]) {
        max = rightNode;
    }
    // 交换位置
    if (max != index) {
        int temp = arr[index];
        arr[index] = arr[max];
        arr[max] = temp;
        // 因为交换位置后有可能使子树不满足大顶堆条件，所以要对子树进行调整
        maxHeap(arr, size, max);
    }
}

/**
 * 堆排序
 * @param arr 待排序的整型数组
 */
public static void heapSort(int[] arr) {
    // 开始位置是最后一个非叶子结点，即最后一个结点的父结点
    int start = (arr.length - 1) / 2;
    // 调整为大顶堆
    for (int i = start; i >= 0; i--) {
        SortTools.maxHeap(arr, arr.length, i);
    }
    // 先把数组中第 0 个位置的数和堆中最后一个数交换位置，再把前面的处理为大顶堆
    for (int i = arr.length - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        maxHeap(arr, i, 0);
    }
}

归并排序

/**
 * 合并数组
 */
public static void merge(int[] arr, int low, int middle, int high) {
    // 用于存储归并后的临时数组
    int[] temp = new int[high - low + 1];
    // 记录第一个数组中需要遍历的下标
    int i = low;
    // 记录第二个数组中需要遍历的下标
    int j = middle + 1;
    // 记录在临时数组中存放的下标
    int index = 0;
    // 遍历两个数组，取出小的数字，放入临时数组中
    while (i <= middle && j <= high) {
        // 第一个数组的数据更小
        if (arr[i] <= arr[j]) {
            // 把更小的数据放入临时数组中
            temp[index] = arr[i];
            // 下标向后移动一位
            i++;
        } else {
            temp[index] = arr[j];
            j++;
        }
        index++;
    }
    // 处理剩余未比较的数据
    while (i <= middle) {
        temp[index] = arr[i];
        i++;
        index++;
    }
    while (j <= high) {
        temp[index] = arr[j];
        j++;
        index++;
    }
    // 把临时数组中的数据重新放入原数组
    for (int k = 0; k < temp.length; k++) {
        arr[k + low] = temp[k];
    }
}

/**
 * 归并排序
 */
public static void mergeSort(int[] arr, int low, int high) {
    int middle = (high + low) / 2;
    if (low < high) {
        // 处理左边数组
        mergeSort(arr, low, middle);
        // 处理右边数组
        mergeSort(arr, middle + 1, high);
        // 归并
        merge(arr, low, middle, high);
    }
}

基数排序

/**
 * 合并数组
 */
public static void merge(int[] arr, int low, int middle, int high) {
    // 用于存储归并后的临时数组
    int[] temp = new int[high - low + 1];
    // 记录第一个数组中需要遍历的下标
    int i = low;
    // 记录第二个数组中需要遍历的下标
    int j = middle + 1;
    // 记录在临时数组中存放的下标
    int index = 0;
    // 遍历两个数组，取出小的数字，放入临时数组中
    while (i <= middle && j <= high) {
        // 第一个数组的数据更小
        if (arr[i] <= arr[j]) {
            // 把更小的数据放入临时数组中
            temp[index] = arr[i];
            // 下标向后移动一位
            i++;
        } else {
            temp[index] = arr[j];
            j++;
        }
        index++;
    }
    // 处理剩余未比较的数据
    while (i <= middle) {
        temp[index] = arr[i];
        i++;
        index++;
    }
    while (j <= high) {
        temp[index] = arr[j];
        j++;
        index++;
    }
    // 把临时数组中的数据重新放入原数组
    for (int k = 0; k < temp.length; k++) {
        arr[k + low] = temp[k];
    }
}

/**
 * 归并排序
 */
public static void mergeSort(int[] arr, int low, int high) {
    int middle = (high + low) / 2;
    if (low < high) {
        // 处理左边数组
        mergeSort(arr, low, middle);
        // 处理右边数组
        mergeSort(arr, middle + 1, high);
        // 归并
        merge(arr, low, middle, high);
    }
}

如果觉得文章对你有用，请随意赞赏

19常用算法.md

https://qc-blog.zust.online/archives/19%E5%B8%B8%E7%94%A8%E7%AE%97%E6%B3%95md

作者

前程QCQCQC

发布于

2023-02-05

更新于

2024-01-28

许可协议

CC BY 4.0