二分查找、快速排序、归并排序（分而治之）

青旅半醒 2023-07-04 08:35 3阅读 0赞

顺序查找

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

二分查找

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

二分查找思想图:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70][]

/***
         *  二分查找
         *  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）是对[冒泡排序][Link 1]的一种改进。 \[1\]

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

应用场景

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

缺点

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

思想图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70 1][]

/**
         * 二叉树快速排序
         * 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）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并][Link 4]。归并排序是一种稳定的排序方法。  
  应用场景  
      数据量大并且有很多重复数据，链式结构  
  缺点  
      需要空间足够大

思想图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70 2][]

/**
         * 归并排序
         * 后序
         * @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++;
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200209141828795.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI=,size_16,color_FFFFFF,t_70
[Link 1]: https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
[Link 2]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695
[Link 3]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200209142933988.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI=,size_16,color_FFFFFF,t_70
[Link 4]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6/253741
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200209144958988.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NkbXhkemI=,size_16,color_FFFFFF,t_70