本文共 4580 字，大约阅读时间需要 15 分钟。

顺序查找

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++;        }    }

转载地址：http://kujdi.baihongyu.com/