1.二分法查找（递归）
public int static binarySearch(int low ,int high,int a[],int key){
int n=a.length;
low=0,high=n-1;
int mid=(low+high)/2;
if(a[mid]==key){
return mid;
}
if(a[mid]<key){
binarySerach(mid+1,high,a,key);
}else{
binarySerach(low,mid+1,a,key);
}
return-1
}
2.二分法查找（循环法）
public int static binarySearch(int a[],int key){
int low=0,high=a.length-1;
while(low<high){
mid=(low+high)/2;
if(a[mid]==key){
return mid;}
if(a[mid]<key){
low=mid+1;}
eles{
high=low-1;}
}
return -1;}
二分法时间复杂度分析：
基本操作次数 数据规模
0 n
1 n/2
2 n/4
: :
k n/2^k
数据规模肯定大于1
所以n/2^k>=1>>>>>>>>>>>k<log2N;
T(n)=O(log2n)
3.插入排序
思想：将整个数组分为有序和无序两个部分，左边为有序，右边为无序，遍历右侧无序数组依次插入左边有序数组中
public void static insertSort(int a[]){
int x;
for(int i=1;i<a.length;i++){
x=a[i];
for(int j=i-1;j>=0;j--){
if(a[j]>x){
//左侧有序从大到小与x比较，将大于x的往后移动一位，将x插入
a[j+1]=a[j];
}else{
return;} }
a[j+1]=x;
}
}
4.选择排序
思想：将线性表看成有序和无序两个部分，与插入排序相同，但是在无序部分找到最小值将其插入到有序部分的末尾(将右端最小值与左端末尾互换）
public static void selectSort(int a[]){
int n=a.length-1,amin ,jmin,temp;
for(int i=0;i<n;i++){
amin=a[i];
for(int j=i+1;j<n;j++){
if(amin>a[j]){
amin=a[j];
jmin=j;}
}
if(amin<a[j]){
temp=amin;
amin=a[j];
a[j]=temp;}
}
}
另一种说法：
取出第一个数与后面比较，比后面大就交换，一轮之后第一个就是最小值
public void selectSort(int a[]){
int temp;
for(int i=0;i<a.length-1;i++){
for(int j=i+1;j<a.length;j++){
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;}
}
}
}
T(n)=n(n-1)/2
5.冒泡排序
思想：将线性表看作有序和无序两部分，但有序在右边，将较大的想序列尾部移动，较小的向序列前部移动
public void static bubbleSort(int a[]){
int temp;
for(int i=a.length-1;i>0;i++){
for(int j=0;j<i;j++){
if(a[j]>a[j+1){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;}
}
}
T(n)=n(n-1)/2
6.快速排序
public static int divide(int a[],int i,int j){
int key=a[i];
while(i<j){
while(i<j&&a[j]>=key) j--;
if(i<j) a[i++]=a[j];
while(i<j&&a[i]<key)i++;
if(i<j)a[j--]=a[i];}
a[i]=key;
return i;}
public static void quickSort(int a[],int low,int high){
if(low<high){
k=divide(a,low.,high);
quickSort(a,low,k-1);
quickSort(a,k+1,high);
}
}
最后，排序的稳定性：若记录序列中有两个或两个以上关键字相等记录，且排序前后他们前后位置不变。
网友评论