基本思想:
將一個規(guī)模為N的問題闪檬，分解成K個規(guī)模較小的子問題星著，這些子問題相互獨立且月原問題性質相同。求解出子問題的解粗悯，合并得到原問題的解虚循。
一、查找技術
1、順序查找
如果線性表為無序表横缔，即表中元素的排列是無序的铺遂，則不管線性表采用順序存儲還是鏈式存儲，都必須使用順序查找茎刚。如果線性表有序襟锐，但采用鏈式存儲結構，則也必須使用順序查找膛锭。
2粮坞、二分查找
image.png
前題條件：數(shù)據(jù)已經排序
注意：設計成左閉右開--是一種區(qū)間無重復的思想random(０，１)等大量的數(shù)學函數(shù)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
應用場景:數(shù)據(jù)量大并且是線性結構
短處:有大量重復數(shù)據(jù)的時候莫杈，性能不好,單向鏈式結構處理性能不好（一般來說，鏈式都不使用）
//快速排序 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
//由于會從兩頭取數(shù)據(jù)奢入，需要一個方向
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
應用場景:數(shù)據(jù)量大并且有很多重復數(shù)據(jù)俊马，鏈式結構
短處:需要空間大
public static void merge(int[] array,int left,int mid,int right){
int leftSize=mid-left;
int rightSize=right-mid+1;
//生成數(shù)組
int[] leftArray=new int[leftSize];
int[] rightArray=new int[rightSize];
//填充數(shù)據(jù)
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
