Java常用算法实现

0.总结

常见算法复杂度.jpg

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)，logn的底数为2

1.归并排序

package DailyPractice;

import java.util.*;
public class Test1 {
    /**
     * 归并排序的思路：先将数组的左边和右边分开排完序之后再合并，
     * 其中左边和右边的排序也是递归用这种先分开排序再合并的思想。
     * 步骤：
     * 1.MergeSort左边
     * 2.MergeSort右边
     * 3.Merge两边（两边的头先开始比较，把较小的放进临时数组，
     * 然后将左边剩余的移进数组，再将右边剩余的移进数组，最后将临时数组覆盖特定部分的旧数组）
     * @param args
     */
    public static void main(String[] args) {
        int[] a = new int[]{2,45,8,147,312,42,478};
        MyMergeSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }

    private static void MyMergeSort(int[] a, int low, int high) {
        int middle = (high+low)/2;
        if (low<high){
            MyMergeSort(a,low,middle);
            MyMergeSort(a,middle+1,high);
            MyMerge(a,low,middle,high);
        }
    }

    private static void MyMerge(int[] a, int low, int middle, int high) {
        int[] temp = new int[high-low+1];
        int i = low;
        int j = middle+1;
        int k = 0;

        //把较小的先移进数组
        while(i<=middle && j <=high){
            if (a[i]<a[j]){
                temp[k++] = a[i++];
            }else {
                temp[k++] = a[j++];
            }
        }

        while(i<=middle){
            temp[k++] = a[i++];
        }

        while (j<=high){
            temp[k++] = a[j++];
        }

        //将新数组覆盖旧数组
        for (int l = 0; l < temp.length; l++) {
            a[l+low] = temp[l];
        }
    }

}

2.快速排序

package DailyPractice;

import java.util.*;
public class Test1 {
    /**
     * 快速排序的思路：首先选择一个锚点，将比他小的数移到他的左边，比他大的数移到右边，
     * 然后用同样的思想对左边和右边进行排序
     * @param args
     */
    public static void main(String[] args) {
        int[] a = new int[]{2,45,8,147,312,42,478};
        MyQuickSort(a,0,a.length-1);
        System.out.println(Arrays.toString(a));
    }

    private static void MyQuickSort(int[] a, int low, int high) {
        if (low>high)return;
        int pivot = a[low];
        int i = low;
        int j = high;
        while (i!=j){
            //记得要先从右边先开始
            while (a[j]>=pivot && i<j){
                j--;
            }
            while (a[i]<=pivot && i<j){
                i++;
            }
            if (i<j){
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[low] = a[i];
        a[i] = pivot;
        MyQuickSort(a, low, i-1);
        MyQuickSort(a,i+1,high);
    }
}

3.选择排序

package DailyPractice;

import java.util.*;
public class Test1 {
    /**
     * 选择排序的思路：首先第一次遍历数组找出最小的数，放在最左边，
     * 第二次遍历找出第二小的数放在第二个位置，依次遍历直到数组排完。
     * 其中的方法是：定一个索引，依次遍历数组，如果比他小的就将索引换为该数的下标，最后如果
     * 索引和一开始的下标不一样就替换。
     * @param args
     */
    public static void main(String[] args) {
        int[] a = new int[]{2,45,8,147,312,42,478};
        MySelectionSort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void MySelectionSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int minIndex = i;
            for (int j = i; j < a.length; j++) {
                if (a[j]<a[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }
    }
}

4.冒泡排序

package DailyPractice.Sort;

public class BubbleSort {
    /**
     * 冒泡排序的思路：多次遍历数组，比较两两相邻的数，如果左边的比右边的大就交换，
     * 直到数组排完序为止。（遍历的次数为(length-1)+(length-2)+(length-3)+...+2+1）
     * @param args
     */
    public static void main(String[] args) {
        int[] arrays = {54,87,2541,7,5462,254};
        int[] res = bubblesort(arrays);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
    }

    private static int[] bubblesort(int[] arrays) {
        for (int i = 0; i < arrays.length-1; i++) {
            for (int j = 0; j < arrays.length - i - 1; j++) {
                if (arrays[j] > arrays[j+1]){
                    int temp = arrays[j];
                    arrays[j] = arrays[j+1];
                    arrays[j+1] = temp;
                }
            }
        }
        return arrays;
    }
}

附：
二分查找，其中的关键点在于mid的选择是用了low+(high-low)/2，而不是(high+low)/2。

package DailyPractice.Search;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1,5,8,9,10,45,98};
        System.out.println(MyBinarySearch(arr,0,arr.length-1,100));
    }

    private static int MyBinarySearch(int[] arr, int low, int high, int target) {
        if (low>high)return -1;

        int mid = low+(high-low)/2;
        if (arr[mid] == target){
            return mid;
        }
        if (arr[mid]<target){
            return MyBinarySearch(arr,mid+1,high,target);
        }
        else {
            return MyBinarySearch(arr,low,mid-1,target);
        }
    }
}

5.算法笔记

• A序列中每个元素离最终的位置都不远，则应使用直接插入排序。
• 快排在序列有序时时间复杂度最差，为O(n²)，在序列有序时时间复杂度最好，为O(nlog₂n)。
• 叶子结点数等于度为2的结点数加1，结点总数等于叶子总数加上度为1的结点数，再加上度为2的结点数。