#include <iostream>
using namespace std;
void mpoSort(int arr[],int len);
void selectSort(int arr[],int len);
void selectSort2(int arr[],int len);
void insertSort(int arr[],int len);
void fastSort(int arr[],int left, int right);
void guiSort(int arr[],int len);
int halfFind(int arr[],int left, int right, int res);
int main()
{
// int arr[10]={63,50,64,95,12,45,68,35,57,65};
int arr[10]={63,23,34,12,45,67,38,53,96,26};
for(int i=0;i<10;i++)
{
cout << arr[i] << " ";
}
cout << endl;
// mpoSort(arr,10);
// selectSort(arr,10);
// selectSort2(arr,10);
// insertSort(arr,10);
fastSort(arr,0,9);
for(int i=0;i<10;i++)
{
cout << arr[i] << " ";
}
cout << endl;
int res = 60;
int pos = halfFind(arr,0,9,res);
printf("the position of %d in the arr is %d\n",res,pos);
return 0;
}
/*冒泡法*/
void mpoSort(int arr[],int len)
{
int N = len;
for(int i=0;i<N-1;i++)
{
int temp;
for(int j=0;j<N-1-i;j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
/*选择法*/
void selectSort(int arr[],int len)
{
int N = len;
for(int i=0;i<N-1;i++)
{
int min = arr[i];
int k = i;
for(int j=i+1;j<N;j++)
{
if(min>arr[j])
{
min=arr[j];
k=j;
}
}
int temp = arr[i];
arr[i] = min;
arr[k] = temp;
}
}
/*选择法*/
void selectSort2(int arr[],int len)
{
int N = len;
for(int i=0;i<N-1;i++)
{
int k = i;
for(int j=i+1;j<N;j++)
{
if(arr[k]>arr[j])
k = j;
}
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
/*插入法*/
void insertSort(int arr[],int len)
{
int N = len;
for(int i=0;i<N-1;i++)
{
int newNum = arr[i+1];
for(int j=i;j>=0;j--)
{
if(arr[j]>newNum)
{
arr[j+1] = arr[j];
}
else
{
arr[j+1] = newNum;
break;
}
}
}
}
/*快速法*/
void fastSort(int arr[],int left,int right)
{
int mid;
int base = arr[left];
int i,j;
for(i=left,j=right;i<j;)
{
while(i<j && arr[j]>base) j--;
if(i<j&&arr[j]<=base) arr[i]=arr[j];
while(i<j && arr[i]<=base) i++;
if(i<j&&arr[i]>base) arr[j]=arr[i];
}
if(i==j)
{
arr[i]=base;
mid = i;
}
if((mid-left)>1) fastSort(arr,left,mid-1);
if((right-mid)>1) fastSort(arr,mid+1,right);
}
/*归并法*/
void guiSort(int arr[],int len)
{
}
/*二分法查找*/
int halfFind(int arr[],int left, int right,int res)
{
int mid=(left+right)/2;
if(left>right) return -1;
if(res==arr[mid]) return mid;
else if(res<arr[mid]) return halfFind(arr,left,mid-1,res);
else return halfFind(arr,mid+1,right,res);
}
评论