算法

参考https://itimetraveler.github.io/2017/07/18/%E5%85%AB%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8Ejava%E5%AE%9E%E7%8E%B0/

二分查找

public class TestBinarySearch {
    private static final int[] arr = {0,1,2,3,4,5,6,7,8,9};

    public static void main(String[] args) {
        System.out.println(binarySearch(arr, 0, arr.length-1 , 3));
    }
    
    private static int binarySearch(int[] arr, int start, int end, int key){
        if(start == end){
            return -1;
        }
        final int mid = (end - start) / 2 + start;
        if(key == arr[mid]){
            return mid;
        } else if(key < arr[mid]){
            return binarySearch(arr, start, mid-1, key);
        } else if(key > arr[mid]){
            return binarySearch(arr, mid+1, end, key);
        }
        return -1;
    }
}

冒泡排序 bubble-sort.gif

冒泡排序需要两个嵌套的循环. 其中, 外层循环移动游标; 内层循环遍历游标及之后(或之前)的元素, 通过两两交换的方式, 每次只确保该内循环结束位置排序正确, 然后内层循环周期结束, 交由外层循环往后(或前)移动游标, 随即开始下一轮内层循环, 以此类推, 直至循环结束.

    static void bubbleSort(int[] array){
        for (int i=array.length; i>0; i--) {
            for(int j=0; j+1<i;j++){
                if(array[j] > array[j+1]){
                    swap(array, j, j+1);
                }
            }
        }
    }

• 选择排序 Selection-Sort-Animation.gif

红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置

    static void selectionSort(int[] arr){
        for(int i=0; i<arr.length; i++){
            int min = i;
            for(int j=i+1; j<arr.length; j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            if(min != i){
                swap(arr, i, min);
            }
        }
    }

1. 从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
   注意要跟min去比较，因为每次循环min的值可能会变，不能跟i比较。

• 插入排序 Insertion-sort-example-300px.gif

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。

insert-sort.gif

    static void insertionSort(int[] arr){
        for(int i=0; i<arr.length-1; i++){
            for(int j=i+1; j>0; j--){
                if(arr[j] < arr[j-1]){
                    swap(arr, j, j-1);
                }
            }
        }
    }
  注意：i<arr.length-1,因为j=i+1,否则无法访问到arr[j]

• 快速排序

基本思想

快速排序的基本思想：挖坑填数+分治法。 Sorting_quicksort_anim.gif
首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

• 代码实现

①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中
递归版的快速排序：通过把基准temp插入到合适的位置来实现分治，并递归地对分治后的两个划分继续快排。那么非递归版的快排如何实现呢？

    public static void main(String[] args) {
        final int[] arr = {3,7,8,5,2,1,9,5,4};
        quick(arr);
    }
    
    private static void print(int[] arr){
        System.out.println();
        for (int iterable_element : arr) {
            System.out.print(iterable_element + " ");
        }
    }

    /**
     * 快速排序
     * 
     * @param numbers
     * 带排序数组
     */
    public static void quick(int[] numbers) {
        if (numbers.length > 0) {
            quickSort(numbers, 0, numbers.length - 1);
        }
    }

    /**
     * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
     * 
     * @param numbers
     *            带查找数组
     * @param low
     *            开始位置
     * @param high
     *            结束位置
     * @return 中轴所在位置
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        int temp = numbers[low]; // 数组的第一个作为中轴
        while (low < high) {
            while (low < high && numbers[high] >= temp) {
                high--;
            }
            numbers[low] = numbers[high];// 比中轴小的记录移到低端
            while (low < high && numbers[low] < temp) {
                low++;
            }
            numbers[high] = numbers[low]; // 比中轴大的记录移到高端
        }
        numbers[low] = temp; // 中轴归位（此时应该是low=high）=》此时才是中轴真正应该所在的位置
        print(numbers);
        return low; // 返回中轴的位置
    }

    /**
     * 
     * @param numbers 带排序数组
     * @param low  开始位置
     * @param high 结束位置
     */
    public static void quickSort(int[] numbers,int low,int high) {
        if(low < high) {
            int middle = getMiddle(numbers,low,high);
            quickSort(numbers, low, middle-1);   
            quickSort(numbers, middle+1, high); 
        }
    }