排序

蛮力法

冒泡排序

2的3次方以内的用冒泡排序

private void BubbleSort(int[] array) {
        for (int j = array.length-1; j >0; j--) {
            boolean flag =true;
            for (int i = 0; i < j; i++) {
                if (array[i] > array[i + 1]) {
                    flag=false;
                    int tmp =array[i+1];
                    array[i+1]=array[i];
                    array[i] =tmp;
                }
            }
            if (flag){
                break;
            }
        }
    }

选择排序

先定位再交换

public class SelectSort {
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            //选出当前序列最小值的index
            int index = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[index] > array[j]) {
                    index = j;
                }
            }
            if (index != i) {
                int tmp = array[index];
                array[index] = array[i];
                array[i] = tmp;
            }
        }
    }
}

递归

斐波那契数列

public static int FibonacciSequence(int i) {
        if (i == 1 || i == 2) {
            return 1;
        } else {
            return FibonacciSequence(i - 1) + FibonacciSequence(i - 2);
        }
    }

调用;

 //斐波那契数列
        for (int i = 1; i < 11; i++) {
            System.out.println( Recursion.FibonacciSequence(i));
        }

输出结果：
1
1
2
3
5
8
13
21
34
55

汉诺塔

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

每次只能移动一个圆盘；
大盘不能叠在小盘上面。
提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

    private void hanoi(int n, int start, int middle, int end) {
        if (n == 1) {
            System.out.println(start + "---------------->" + end);
        } else {
            hanoi(n - 1, start, end, middle);
            System.out.println(start + "---------------->" + end);
            hanoi(n - 1, middle, start, end);
        }
    }

调用：

hanoi(3, 1, 2, 3);

输出：

1---------------->3
1---------------->2
3---------------->1
1---------------->3
2---------------->3
2---------------->1
3---------------->2

分治法

顺序查找

二分查找

首先这个序列必须是有序的

int [] test ={1,2,3,4,7,9,10,12};

/**
     * 二分查找  
     * @param array  数据
     * @param startIndex  开始位置交标
     * @param endIndex 结束位置交标
     * @param key 寻找的数字
     * @return 数字所在的交标  返回负值表示异常
     */
    private int binarySearch(int[] array, int startIndex, int endIndex, int key) {
        if (startIndex < 0 || endIndex < 0 || startIndex >= endIndex || endIndex > array.length) {
            return -1;
        }
        int low = startIndex;
        int high = endIndex-1;//遵循左闭右开原则
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midValue = array[mid];
            if (key < midValue) {
                high = mid - 1;
            } else if (key > midValue) {
                low = mid + 1;
            } else {
                return mid;
            }
        }
        return -(low + 1);
    }

快速排序

应用场景：数据量大并且是线性排序。
注意：不要在链式结构中使用，重复数据过多也不合适

/**
     * 快速排序
     *
     * @param array
     * @param begin
     * @param end
     */
    private static void quickSort(int[] array, int begin, int end) {
        if (end - begin <= 1) {
            return;
        }
        int x = array[begin];//暂存枢纽
        int low = begin;
        int high = end;
        boolean direction = true;//排序方向  true:为从右往左  false:从左往右
        L1:
        while (low < high) {
            if (direction) {//从右往左
                for (int i = high; i > low; i--) {
                    if (array[i] <=x) {
                        array[low++] = array[i];
                        high = i;
                        direction = !direction;//切换方向
                        continue L1;
                    }
                }
                high = low;
            } else {
                for (int i = low; i < high; i++) {
                    if (array[i] >= x) {
                        array[high--] = array[i];
                        low = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                low = high;
            }

        }
        //把最后找到的值放入中间位置
        array[low] = x;

        //开始完成左右两边的操作 二叉树的前序遍历
        quickSort(array, begin, low - 1);
        quickSort(array, begin + 1, end);

    }

输出结果：
31 68 45 90 23 39 54 12 87 76
12 23 31 39 45 54 68 76 87 90

归并排序

解决快排不能操作单链表的问题，但是空间牺牲大

 /**
     * 归并排序
     *
     * @param array
     * @param left
     * @param right
     */
    public static void mergeSort(int[] array, int left, int right) {
        if (left == right) {
            return;
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);//排好左边
            mergeSort(array, mid + 1, right);//排好右边
            merge(array, left, mid + 1, right);//再对左右进行合并
        }
    }


    /**
     * 通过拆分数组合并数据来对数据排序
     *
     * @param array
     * @param left
     * @param mid
     * @param right
     */
    public static void merge(int[] array, int left, int mid, int right) {
        int leftSize = mid - left;
        int rightSize = right - mid + 1;

        //开始生产数组
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        // 填充左边数组
        for (int i = left; i < mid; i++) {
            leftArray[i - left] = array[i];
        }

        //填充右边数组
        for (int i = mid; i <= right; i++) {
            rightArray[i - mid] = array[i];
        }


        //合并数组
        int i = 0;
        int j = 0;
        int k = left;

        while (i < leftSize && j < rightSize) {
            if (leftArray[i] < rightArray[j]) {
                array[k++] = leftArray[i++];
            } else {
                array[k++] = rightArray[j++];
            }
        }
        //表示左边还有数据没有合并完
        while (i < leftSize) {
            array[k++] = leftArray[i++];
        }

        //表示右边边还有数据没有合并完
        while (j < rightSize) {
            array[k++] = rightArray[j++];
        }

    }

插入

直接插入排序

在已经有序的数据中，插入一个数据，使用插入排序效率是非常高的。比如纸牌和麻将

 /**
     * 直接插入排序
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int  j =i;
            int target =array[i];
            while (j>0 &&target<array[j-1]){
                array[j]=array[j-1];
                j--;
            }
            array[j]=target;

        }
    }

希尔排序

对插入排序进行优化，增加了一个步长

/**
     * 希尔排序
     *
     * @param array
     * @param step  步长
     */
    public static void shellSort(int[] array, int step) {
        for (int k = 0; k < step; k++) {//k 是对步长的一个定位，选择每次操作的开始位置
            for (int i = k + step; i < array.length; i = i + step) {
                int j = i;
                int target = array[i];
                while (j > step - 1 && target < array[j - step]) {
                    array[j] = array[j - step];
                    j=j-step;
                }
                array[j] = target;
            }
        }
    }