从零开始学数据结构和算法 -(五)- 分治法 -(二分查找、快速排序、归并排序)

动画演示

需求： 找到有序表里面的 “ 1 ”

代码

/**

• 二分查找*/public static int binarySearch(int[] array,int fromIndex,int toIndex,int key){int low=fromIndex;int high=toIndex-1;while(low<=high){int mid=(low+high)/2;//取中间 int midVal=array[mid];if(key>midVal){//去右边找 low=mid+1;}else if(key<midVal){//去左边找 high=mid-1;}else{return mid;}}return -(low+1);//low+1 表示找不到时停在了第 low+1 个元素的位置}

快速排序

概念

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

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

动画演示

代码实例

//快速排序 31 21 59 68 12 40// x=31public static void quickSort(int[] array,int begin,int end){if(end-begin<=0) return;int x=array[begin];int low=begin;//0int high=end;//5//由于会从两头取数据，需要一个方向 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;//如果上面的 if 从未进入，让两个指针重合}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);}

归并排序

概念

• 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法思路

• 归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如?设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为 14；

动画演示

上代码

@Testpublic void test(){int[] array=new int[]{2,1,6,4,3,9,8,10,7,5};