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

本文主要是介绍二分查找、快速排序、归并排序（分而治之），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

顺序查找

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

 

这篇关于二分查找、快速排序、归并排序（分而治之）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---