随笔 - 8, 文章 - 1, 评论 - 14, 引用 - 0
数据加载中……

基础排序查找算法


  二分查找:
 binarysearch考的比较多,它适用于已经排序的元素中的查找

 int binarySearch(int a[],int len,int value)
{
    int low = 0;
    
int high = len -1;    
    
    
while(low<=high)   //注意搜索条件,有可能两者会相等
    {
        
int mid = (low+high)/2;
        
if(a[mid]==value) return mid;
        
else if(a[mid]>value) high = mid -1;            
        
else low = mid + 1;    
    }
    
return -1;
}

int main()
{
    
int a[] = {1,2,3,4,5,6,7,8,9,10};
    
int rec = binarySearch(a,10,4);
    
if(rec==-1)
        printf(
"Not found\n");
    
else
        printf(
"value is found %d \n",rec);
    
return 0;
}
 
 快速排序
 对冒泡算法的扩展
 
  int partition(int a[],int low,int high)
{
    int temp = a[low];
    
while(low<high)
    {
        while(low<high && a[high]>=temp) --high;
        a[low] 
= a[high];
        
while(low<high && a[low]<=temp)  ++low;
        a[high] 
= a[low];
    }
    
    a[low] 
= temp;
    
return low;
}
    



void Qsort(int a[],int begin,int end)
{
    
int rec;
    
if(begin<end)
    {
        rec 
= partition(a,begin,end);
        printf(
"rec is %d\n",rec);                
        Qsort(a,begin,rec
-1);
        Qsort(a,rec
+1,end);
    }
}

int main()
{
    
int  a[] = {1,4,0,-3,90,7,9,23};
    Qsort(a,
0,7);
    
int i =0;
    
for(;i<8;i++)
        printf(
"%d\t",a[i]);

    
return 0;
}
 
  
  

posted on 2011-08-19 18:24 兵临城下 阅读(111) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理