概念
- 二分查找也称折半查找(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;