上午写了个第四题,写的不好大家轻砸,供有需的朋友参考。
[C++] 纯文本查看 复制代码 // 快排加二分查找.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<stdlib.h>
#include<iostream>
#include<ctime>
using namespace std;
#define N 100
int a[N];
int key;
int Partition(int arr[],int low,int high)//分割
{
int pivotkey;
pivotkey = arr[low];
while( low<high )
{
while( low<high && arr[high]>=pivotkey )
--high;
arr[low] = arr[high];
while( low<high && arr[low]<=pivotkey )
++low;
arr[high] = arr[low];
}
arr[low] = pivotkey;
return low;
}
void qsort(int arr[],int low,int high)
{
int pivotloc;//枢轴
if( low<high )
{
pivotloc = Partition(arr,low,high);
qsort(arr,low,pivotloc-1);
qsort(arr,pivotloc+1,high);
}
}
int Search_Bin(int arr[],int low,int high,int key)
{
int mid;
while( low<=high )
{
mid = ( low+high )/2;
if ( arr[mid] == key )
{
return mid;
}
else if( arr[mid] > key )
{
high = mid - 1;
}
else
low = mid + 1;
}
return 0;
}
int main()
{
srand((unsigned)time(NULL));
for(int i=0;i<N;i++)
{
a[i]=rand()%100;
}
int startnum=0;
int len=N;
qsort(a,startnum,len);
cout<<"快排结果"<<endl;
for(int i=0;i<N;i++)
{
cout<<a[i]<<' ';
}
cout<<"请输入要查找位置的数字"<<endl;
cin>>key;
cout<<Search_Bin(a,startnum,len,key)<<endl;
system("pause");
}
|