|
今天闲来无事，写写快速排序与二分查找的代码，也给自己回顾一篇。
以下的代码都是我经vc2005 测试通过的。
//划分区间函数 最主要的函数
int Partitionfun(int * intarray,int i,int j)
{
int key = intarray[i]; //排序的主元值
while(i<j)
{
while(i<j&&intarray[j]>=key) j--;
if (i<j)
{
intarray[i]= intarray[j];
i++;
}
while(i<j&&intarray[i]<=key) i++;
if (i<j)
{
intarray[j] = intarray[i];
j--;
}
}
intarray[i]= key;
return i;
}
//递归调用上面的函数
void QuickSort(int * intarray,int i,int j)
{
int midpos;
if (i<j)
{
midpos= Partitionfun(intarray,i,j);
QuickSort(intarray,i,midpos-1);
QuickSort(intarray,midpos+1,j);
}
}
//二分查找
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
int BinarySearch(int * pArray,int pKey,int pStart,int pEnd)
{
int midd;
while(pStart<=pEnd) // 注意事项 别写成了小于了，这样查询最后的元素有问题
{
midd=(pStart+pEnd)/2;
if (pArray[midd]==pKey)
{
return midd;
}else if(pArray[midd]>pKey)
{
pEnd = midd-1; //记得-1（不然死循环）
}else
{
pStart= midd+1; //记得+1 （不然死循环）
}
}
return midd;
}
//查找数组第2大值
int FindSecond(int * pArray,int len)
{
int sencond = 0;
int maxValue = pArray[0];
for(int i=1;i<len;i++)
{
if (maxValue<pArray[i])
{
sencond = maxValue;
maxValue=pArray[i];
}else if (pArray[i]>sencond)
{
sencond = pArray[i];
}
}
return sencond;
}
程序调用
void main()
{
cout<<"hello word!"<<endl;
int intarray[]={12,52,36,22,11,44,5,22,336,2,25,3,6,25,1,4,8,5,4,11,44,55,66,33,22,44,77,55,22,11,44,55,66,5,5555,22222,11111,777777,444444,11111,111,
5555,5555,66666,333333,22222,11111,44444,77777,454444,555555,444444111,1111144,1144};
QuickSort(intarray,0,sizeof(intarray)/sizeof(int)-1);
for (int i=0;i<sizeof(intarray)/sizeof(int);i++)
{
cout<<intarray[i]<<endl;
}
cout<<BinarySearch(intarray,444444111,0,sizeof(intarray)/sizeof(int)-1)<<endl;
} | 
转播
