java常用算法

1. 快速排序

平均时间复杂度为O（n×log（n））

package com.young4j.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int i;
        int a[] = { 30, 40, 60, 10, 20, 50 };

        System.out.printf("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("
");

        quickSort(a, 0, a.length - 1);

        System.out.printf("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("
");
    }


    /*
     * 快速排序
     *
     * 参数说明： a -- 待排序的数组 l -- 数组的左边界(例如，从起始位置开始排序，则l=0) r --
     * 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    public static void quickSort(int[] a, int l, int r) {

        if (l < r) {
            int i, j, x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while (i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if (i < j)
                    a[i++] = a[j];
                while (i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if (i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quickSort(a, l, i - 1); /* 递归调用 */
            quickSort(a, i + 1, r); /* 递归调用 */
        }
    }
}

2. 冒泡排序

平均时间复杂度为O(n²)

package com.young4j.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 * 
 * 依次比较相邻的两个数，如果第一个大于第二个，就交换他们的位置，
 * 将小数放在前边，大数放到后边。
 * 
 * 第一趟冒泡完毕后，最后一个数一定是数组中最大的一个数，
 * 所以最后一趟冒泡时最后一个数不参与，以此类推。
 * 
 * N个数字要排序完成，总共进行N-1趟排序，
 * 每i趟的排序次数为(N-i)次，所以可以用双重循环语句，
 * 外层控制循环多少趟，内层控制每一趟的循环次数。
 * 
 * 每进行一趟排序，就会少比较一次，
 * 因为每进行一趟排序都会找出一个较大值。
 * 
 * 时间复杂度：
 * 如果我们的数据正序，只需要走一趟即可完成排序。
 * 所需的比较次数C和记录移动次数M均达到最小值，
 * 即：Cmin=n-1;Mmin=0;所以，
 * 冒泡排序最好的时间复杂度为O(n)。
 * 如果很不幸我们的数据是反序的，则需要进行n-1趟排序。
 * 每趟排序要进行n-i次比较(1≤i≤n-1)，
 * 且每次比较都必须移动记录三次来达到交换记录位置。
 * 在这种情况下，比较和移动次数均达到最大值：
 * 最坏时间复杂度为：O(n2) 
 * @author 程序员的365
 *
 */
public class BubbleSort {
    public static void main(String[] args) {
        int [] numbers = {3,4,6,1,8};
        bubbleSort(numbers);
    }
    public static void bubbleSort(int[] numbers) {
        int temp = 0;
        int size = numbers.length;
        for(int i = 0; i< size - 1; i ++) {
            for(int j = 0; j < size -1 -i; j ++) {
                if(numbers[j] > numbers[j + 1]) {
                    temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
        Arrays.stream(numbers).forEach(n -> System.out.println(n));
    }
}

3. 插入排序

package com.young4j.sort;
/**
 * 直接插入排序
 * 
 * 插入排序就是将当前待排序的元素插入到一个已经排序好的列表里。比较形象的例子就是右手抓取一张扑克，将它
 * 插入到左手拿着的排序好的一堆扑克里边。时间复杂度为O(n2)，空间复杂度O(1)，并不是最优的排序算法，特点为：简单，无需额外存储空间。
 * 如果元素包含的内容过大，就不适合直接插入排序，因为直接插入排序需要移动元素的次数比较多.
 * 
 * 基本思想：
 * 将n哥待排序的元素看成一个有序列表和一个无序列表，开始有序列表中只有一个元素，无序列表中有n-1个元素。
 * 每次从无序列表中取出第一个元素，将它插入到有序列表中，使之成为新的有序列表，重复n-1次完成整个排序。
 * @author YF
 *
 */

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class InsertionSort {
    Logger logger = LoggerFactory.getLogger(this.getClass());
    public static void main(String[] args) {
        int a[] = {31,25,78,12,41,19,6,1};
        new InsertionSort().insertionSort(a);
    }
    /**
     * 直接插入排序算法
     * @param args
     */
    private void insertionSort(int [] args) {
        logger.info("--------------------------直接插入排序算法--------------------------");
        int n = args.length;
        int i,j;
        for(i = 1;i < n;i ++) {
            //本次排序待插入有序列表中的元素
            int temp = args[i];
            //将temp插入有序列表中正确的位置,从后往前循环，将大于待插入的数向后移动
            for(j = i - 1;j >= 0 && args[j] > temp;j --) {
                //将待插入元素后移，为插入temp做准备
                args[j + 1] = args[j];
            }
            //插入temp
            args[j + 1] = temp;
            print(args,n,i);
        }
         printResult(args,n);
    }
    /**
     * 打印排序的最终结果
     * @param a
     * @param n
     */
    private void printResult(int[] a, int n){
        System.out.print("最终排序结果：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
    /**
     * 打印排序的每次循环的结果
     * @param a
     * @param n
     * @param i
     */
    private void print(int[] a, int n, int i) {
        // TODO Auto-generated method stub
        System.out.print("第"+i+"次：");
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
    
}

4.二分查找

二分查找平均时间复杂度O(log2n)

package com.young4j.search;

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={5,3,6,1,9,8,2,4,7};
        bubleSort(arr);
        Arrays.stream(arr).forEach(n -> System.out.println(n));
        
    }
    /**
     * 冒泡排序
     * 1.如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
     * 2.如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
     * @param arr
     * @return
     */
    public static void bubleSort(int[] arr) {
        int temp = 0;
        for(int i = 0; i < arr.length - 1; i ++) {
            for(int j = 0; j < arr.length - 1 -i; j ++) {
                if(arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j]     = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    public static int binarySearch(int[] arr,int num) {
        int low = 0;
        int upper = arr.length - 1;
        while(low <= upper) {
            int mid = (low + upper) / 2;
            if(num > arr[mid]) {
                low = mid + 1;
            }else if(num < arr[mid]) {
                upper = mid - 1;
            }else {
                return arr[mid];
            }
        }
        return -1;
    }
}