二分查找、快速排序、归并排序（分而治之）_什么是归并排序和二分搜寻

顺序查找

1.   如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。
2.   如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。

二分查找

       必须遵循两个条件：数组有序、符合左闭右开原则(是一种区间无重复的思想)

      二分查找思想图:

 

 /***
     *  二分查找
     *  binary search ,this  is  must be  order  array
     * @param array  源数组
     * @param fromIndex  开始索引
     * @param toIndex  结束索引
     * @param key  值
     * @return
     */
    public static int binarySearch(int[] array, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        /**左开右闭原则,保持连续空间**/
        int high = toIndex - 1;
        while (low <= high) {
            /**查找中间的数**/
            int midIndex = (low + high) >> 1;
            int midValue = array[midIndex];
            /**如果大于中间数，左边查找**/
            if (key > midValue) {
                low = midIndex + 1;
                /**如果小于中间数，右边查找**/
            } else if (key < midValue) {
                high = midIndex - 1;
            } else {
                return midIndex;
            }
        }
        /**low+1表示找不到时停在了第low+1个元素的位置**/
        return -(low + 1);
    }

快速排序  

       快速排序（Quicksort）是对冒泡排序的一种改进。 [1] 

        快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

     应用场景

          数据量大并且是线性结构。

     缺点

1.  有大量重复数据的时候，性能不好
2.  单向链式结构处理性能不好（链式不建议不使用）

思想图：

    

 

 /**
     * 二叉树快速排序
     * quick sort ,this is  out of order
     *  其实就是中序的排法
     *
     * @param array
     * @param begin 开始
     * @param end   结束
     */
    public static void quickSortArray(int[] array, int begin, int end) {
        if (end - begin <= 0) return;
        int x = array[begin];
        int low = begin;
        int high = end;
        /**由于会从两头取数据，设置一个方向的标识位**/
        boolean direction = true;
        L:/**标签，跳出这个循环的位**/
        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 L;
                    }
                }
                /**上面条件不成立，说明指针重合了**/
                high = low;
            } else {
                for (int i = low; i < high; i++) {
                    if (array[i] >= x) {
                        array[high--] = array[i];
                        low = i;
                        direction = !direction;
                        continue L;
                    }
                }
                /**上面条件不成立，说明指针重合了**/
                low = high;
            }
        }
        /**把最后找到的值 放入中间位置
         开始完成左右两边的操作**/
        array[low] = x;
        quickSortArray(array, begin, low - 1);
        quickSortArray(array, low + 1, end);
    }

归并排序

        归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
  应用场景
      数据量大并且有很多重复数据，链式结构
  缺点
      需要空间足够大

思想图：

  

 /**
     * 归并排序
     * 后序
     * @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;
            /**相当于后序排序 LRD
             * 最底层拆分对比
             *    左边到中间->中间到右边->归并
             * **/
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid + 1, right);
        }
    }
 
    /***
     *   array  归并
     * @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;
        /**拆分两个数组，填充数据，下标以index开始**/
        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];
                k++;
                i++;
            } else {
                array[k] = rightArray[j];
                k++;
                j++;
            }
        }
        /**如果左边还有剩下的，直接cpoy**/
        while (i < leftSize) {
            array[k] = leftArray[i];
            k++;
            i++;
        }
        /**如果右边还有剩下的，直接cpoy**/
        while (j < rightSize) {
            array[k] = rightArray[j];
            k++;
            j++;
        }
    }