概念

• 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

优点

• 查找速度快

缺点

• 待查表为有序表

算法思路

• 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

动画演示

需求： 找到有序表里面的 “ 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=31

public static void quickSort(int[] array,int begin,int end){

if(end-begin<=0) return;

int x=array[begin];

int low=begin;//0

int 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；

归并。

算法思路

• 归并操作(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；