【Java 入门】（四）算法

算法作为入门必备，要学好真的需要比较好的数学基础和逻辑，对于一些常见的排序算法，如果真的学不会背也要背下来，因为这是基础，面试的笔试中肯定会有一两个算法题。

下面介绍几种常见常考的算法：

冒泡算法

其大体思想就是通过与相邻元素的比较，然后把较小的数交换到最前面，这个过程类似于水泡向上升一样。考点：冒泡排序的时间复杂度为O(n^2)

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}

快速排序

其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较，把最小的冒泡到最顶端。而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面，同时也把大数沉到下面。考点：快速排序是不稳定的，其平均时间复杂度是O(nlgn)

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

二分查找

有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。

public static int biSearch(int []array, int a) {
        int lo = 0;
        int hi = array.length - 1;
        int mid;
        while(lo <= hi){
            mid = (lo+hi) / 2;
            if(array[mid] == a) {
                return mid + 1;

            }else if(array[mid] < a) {
                lo=mid+1;

            }else{

                hi=mid-1;
            }
        }

        return -1;
}

无论是哪种算法，最重要的是要理解它的核心思想，一般的项目中，说实话也很少会用到上面说的这些排序算法了。

我们接触到的可能更多的是来源于业务方面的，例如敏感词的过滤，我们一般用到DFA算法。又例如比较两个内容的相似度，我们可能用到相似度算法（Levenshtein Distance）等等。

如果大家对算法或者数学很有兴趣的，推荐大家看一本书<数学之美>

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/93629.html