分治法

二分查找

在android的SparseArray中get方法就是通过二分法查找到结果。
二分查找的前提是有一个已经排好序的数组。

二分查找

思路：假设我们需要查找22这个值在数组中的位置，如上图的数组，取数组的中间下标5中的值，为21，用目标值22跟21做对比，22大于21，就在右边继续查找22这个值，否则在左边查找。
接着再从剩下的数组大小中同理取一半的下标为8，值是62同目标22对比大于22，这在右边查找。以此类推，直到找到目标22为止，返回22的下标。没找到返回负 1。

 public void Test(){
        int[] array = {4,7,8,10,14,21,22,36,62,77,81,91};
        int key = 22;
        System.out.println(binarySearch(array,0,array.length,key));
    }

/**
     * 在array中从start到end查找有没有key这个值
     * @param array
     * @param start
     * @param end
     * @param key
     */
    private int binarySearch(int[] array,int start,int end,int key){
        int lo = 0;
        int low = start;
        int hight = end -1;

        while (low < hight){
            int mid = (low + hight)>>>1;
            int midVal = array[mid];
            if (midVal <key){
                low = mid +1;
            }else if (midVal > key){
                hight = mid -1;
            }else {
                return mid;
            }

        }
        return ~lo;
    }

输出结果就是 6

也有使用递归的思想去实现二分查找，但不建议这样做。

 /**
     *  递归实现二分查找
     * @param array
     * @param start
     * @param end
     * @param key
     * @return
     */
    private int binarySearch2(int[] array,int start,int end,int key){
        int mid = (start+end)>>>1;
        if (array[mid] == key){
            return mid;
        }
        if (start <end){
            if (array[mid] < key){
                return binarySearch2(array,mid + 1,end,key);
            }else if (array[mid] > key){
                return binarySearch2(array,start,mid - 1,key);
            }
        }
        return 0;
    }

快速排序
应用场景：大量数据并且是线性结构。
短处：
1、有大量重复数据，性能不好。
2、单向链式结构处理性能不好（一般来说，链式都不使用）

排序排序的思想：

给一组数据进行排序，首先把左边第一个值暂存在T上。

在数组两端各定义一个指针(就叫指针吧，好理解)。

移动high指针取值，然后跟T中存的数据比对(这里是31)。

如果high指针取的值(12)比暂存的值(31)小。

就替换low指针指向的值。

接着换low指针移动跟暂存的值(31)做对比。

如果low指向的值(68)比暂存值(31)大。

就把high指向的值替换为low的值。

接着再次更换移动的指针为high。

同样的指针指向的值(23)比暂存值(31)小，就替换。

用high指针的值替换low指针的值。

同理，再次切换指针移动，比暂存值大就往high指针替换，比暂存值小就往low指针替换。

最后两个指针指到了同一个值上。

把暂存值替换上去。

这样第一轮的排序完成，31左边的都比它小，右边的都比它大。
然后排序左边和右边，实现整个数组的排序。

  public void testQuickSort(){
        int[] array = new int[]{31,68,45,90,23,39,54,12,87,76};
        quickSort(array,0,array.length-1);
        for (int i = 0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }

 private void quickSort(int[] array,int begin,int end){
        if ((end - begin)<=0) return;
        int x = array[begin];
        int low = begin;
        int high = end;
        //由于会从两个方向取数据，需要定义一个方向；
        boolean direction = true;
        //开始排序
        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,low+1,end);

    }

归并排序
思想：

应用场景：数据量大并且是链式结构。
短处：需要空间大。

 public static void mergeSort(int[] array, int left, int right) {
        if (left == right) {
            return;
        } else {
            int mid = (left + right) >>> 1;
            mergeSort(array, left, mid);//排好左边  L
            mergeSort(array, mid + 1, right);//排好右边  R
            merge(array, left, mid + 1, right);//再对左右进行合并 D
        }
    }

//归并排序
    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) {
            //右边还有数据没用完
            System.out.print("k：" + k);
            System.out.print("length：" + array.length);
            array[k++] = rightArray[j++];
        }
    }