C++ 先對(duì)數(shù)組排序,在進(jìn)行折半查找

2020-01-26 15:43:37

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

第一步：輸入15個(gè)整數(shù)

第二步：對(duì)這15個(gè)數(shù)進(jìn)行排序

第三部：輸入一個(gè)數(shù)，在后在排好序的數(shù)中進(jìn)行折半查找，判斷該數(shù)的位置

實(shí)現(xiàn)代碼如下：

方法一：

選擇排序法+循環(huán)折半查找法

復(fù)制代碼代碼如下:

#include<iostream>
using namespace std;
int main(){
 int a[15];
 int n,i;
 void array_sort(int a[], int n);
 int zeban(int a[], int start ,int end,int n);
 cout<<"Please input 15 numbers:"<<endl;
 for(i=0;i<15;i++){
  cin>>a[i];
 }
 cout<<"Sorted order:"<<endl; 
 //==============選擇排序======== 
 array_sort(a,15);
 //=======輸出排序完成的數(shù)組==== 
    for(i=0;i<15;i++){
  cout<<a[i]<<" ";
  }
 cout<<endl;
 cout<<"please input a number:";
 cin>>n;
 //================折半查找========== 
 cout<<endl;
 cout<<"number "<<n<<" locate in "<<zeban(a,0,14,n)<<endl;
 return 0;
}
void array_sort(int a[],int n){
 int i,j,k,tool;
     for(i=0;i<n;i++){
  k=i;
  for(j=(i+1);j<n;j++){
  if(a[j]<a[k]){
     k=j;
        }
  }
  tool=a[i];
  a[i]=a[k];
  a[k]=tool;
  }
}
int zeban(int a[],int start,int end,int n){
 int tag=-1;
 for(start=0,end=14;start<=end;){
  if(n==a[(start+end)/2]){
   tag=(start+end)/2+1;
   return tag;
  }else if(n<a[(start+end)/2]){
   end=(start+end)/2;
  }else if(n>a[(start+end)/2]){
   start=(start+end)/2;
  }
 }
}

第二種方法：

冒泡排序法+遞歸折半查找法

復(fù)制代碼代碼如下:

#include<iostream>
using namespace std;
int main(){
 int a[15];
 int n,i;
 void array_sort(int a[], int n);
    int IterBiSearch(int data[], const int x, int beg, int last); 
 cout<<"Please input 15 numbers:"<<endl;
 for(i=0;i<15;i++){
  cin>>a[i];
 }
 cout<<"Sorted order:"<<endl; 
 //==============選擇排序======== 
 array_sort(a,15);
 //=======輸出排序完成的數(shù)組==== 
    for(i=0;i<15;i++){
  cout<<a[i]<<" ";
  }
 cout<<endl;
 cout<<"please input a number:";
 cin>>n;
 //================折半查找========== 
 cout<<endl;
 cout<<"number "<<n<<" locate in "<<IterBiSearch(a,n, 0, 14)<<endl;
 return 0;
}
void array_sort(int a[],int n){
 int i,j,tool;
     for(i=0;i<n;i++){
     for(j=0;j<(n-i-1);j++){
        if(a[j]>a[j+1]){
           tool=a[j];
           a[j]=a[j+1];
           a[j+1]=tool;
        }
     }
    }
}
int IterBiSearch(int data[], const int x, int beg, int last)  
{  
    int mid = -1;  
    mid = (beg + last) / 2;  
    if (x == data[mid])  
    {  
        return (mid+1);  
    }  
    else if (x < data[mid])  
    {  
        return IterBiSearch(data, x, beg, mid - 1);  
    }  
    else if (x > data[mid])  
    {  
        return IterBiSearch(data, x, mid + 1, last);  
    }  
    return -1;  
}  