java基本算法

还怕大雨吗. 2022-02-15 07:31:35 10636 0 0 0

理解算法之前必须要先理解的几个算法的概念:

空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。

时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。

稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。

一、**二分查找算法**
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。这个是基础,最简单的查找算法了。

/**
 * @author qusongyun
 */
public class DichotomySearch {

    public static void main(String[] args) {
        int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        System.out.println(binSearch(srcArray, 28));
    }
    /**
     * 二分查找普通循环实现
     *
     * @param srcArray 有序数组
     * @param key 查找元素
     * @return
     */
    public static int binSearch(int srcArray[], int key) {
        int mid = srcArray.length / 2;
//        System.out.println("=:"+mid);
        if (key == srcArray[mid]) {
            return mid;
        }

//二分核心逻辑
        int start = 0;
        int end = srcArray.length - 1;
        while (start <= end) {
            mid = (end - start) / 2 + start;
            if (key < srcArray[mid]) {
                end = mid - 1;
            } else if (key > srcArray[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。

二、递归算法
递归简单理解就是方法自身调用自身。

/**
 * @author qusongyun
 */
public class RecursionSearch {
    public static void main(String[] args) {
        int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        System.out.println(binSearch(srcArray, 0,15,28));
    }
    /**
     * 二分查找递归实现
     *
     * @param srcArray  有序数组
     * @param start 数组低地址下标
     * @param end   数组高地址下标
     * @param key  查找元素
     * @return 查找元素不存在返回-1
     */
    public static int binSearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }
}

递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。

这里就不过多阐述,有兴趣的可以继续了解下8大算法
一、直接插入排序(Insertion Sort)
二、希尔排序(Shell Sort)
三、选择排序(Selection Sort)
四、堆排序(Heap Sort)
五、冒泡排序(Bubble Sort)
六、快速排序(Quick Sort)
七、归并排序(Merging Sort)
八、基数排序(Radix Sort)