基本思想:
将一个规模为N的问题，分解成K个规模较小的子问题，这些子问题相互独立且月原问题性质相同。求解出子问题的解，合并得到原问题的解。
一、查找技术
1、顺序查找
如果线性表为无序表，即表中元素的排列是无序的，则不管线性表采用顺序存储还是链式存储，都必须使用顺序查找。如果线性表有序，但采用链式存储结构，则也必须使用顺序查找。
2、二分查找
image.png
前题条件：数据已经排序
注意：设计成左闭右开--是一种区间无重复的思想random(０，１)等大量的数学函数for(int i=0;i<array.length;i++）
/**
* 二分查找
*/
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个元素的位置
}
测试代码
int array[] = {1,2,3,4,5,6,7,8};
int index0 = binarySearch(array, 0, array.length, 0);
int index1 = binarySearch(array, 0, array.length, 1);
int index4 = binarySearch(array, 0, array.length, 4);
int index8 = binarySearch(array, 0, array.length, 8);
System.out.println("0的下标:"+index0);
System.out.println("1的下标:"+index1);
System.out.println("4的下标:"+index4);
System.out.println("8的下标:"+index8);
打印结果
0的下标:-1
1的下标:0
4的下标:3
8的下标:7
二、快速排序（前序）
image.png
应用场景:数据量大并且是线性结构
短处:有大量重复数据的时候，性能不好,单向链式结构处理性能不好（一般来说，链式都不使用）
//快速排序 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);
}
测试代码
int arrays[] = {0,2,3,4,5,6,9,7,1};
quickSort(arrays,0,arrays.length-1);
for (int i = 0; i < arrays.length; i++) {
System.out.print(arrays[i]+" ");
}
打印结果
0 1 2 3 4 5 6 7 9
三、归并排序(后序)
image.png
应用场景:数据量大并且有很多重复数据，链式结构
短处:需要空间大
public static void merge(int[] array,int left,int mid,int right){
int leftSize=mid-left;
int rightSize=right-mid+1;
//生成数组
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++;
}
}
while(i<leftSize){
array[k]=leftArray[i];
k++;i++;
}
while(j<rightSize){
array[k]=rightArray[j];
k++;j++;
}
}
public static void mergeSort(int array[],int left,int right){
if(left==right){
return;
}else{
int mid=(left+right)/2;
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
merge(array,left,mid+1,right);
}
}
int[] array=new int[]{2,1,6,4,3,9,8,10,7,5};
mergeSort(array,0,array.length-1);
for (int i : array) {
System.out.print(i+" ");
}
打印结果
1 2 3 4 5 6 7 8 9 10
网友评论