随笔 - 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:28 兵临城下 阅读(1522) 评论(4)  编辑 收藏 引用 所属分类: 算法

评论

# re: 基础排序查找算法[未登录]  回复  更多评论   

这种二分查找除了考试几乎没有一点实用价值。通常使用的二分查找用于找一个序列的上界或下界。请到我主页上看看原地归并排序,有二分查找的相关代码。

用第一个元素做支点进行划分,请想一想当待排序序列为逆序时它将退化成冒泡排序,那会有多慢吧?就算用随机序列,这种快速排序恐怕也慢的不能接受,请到我主页上看看快速排序的前两个版本怎么设计的,就算最慢的原始版本(第3个版本),相信也会比你的这种快排快得多。

唉,可恶的中国计算机教育啊,误人子弟一批又一批,不知道还会继续多少批...
2011-08-19 21:26 | Chipset

# re: 基础排序查找算法  回复  更多评论   

不全啊
2011-08-19 23:07 | 向振伟

# re: 基础排序查找算法  回复  更多评论   

@Chipset

这种二分查找除了考试几乎没有一点实用价值??????????????? 上层做多的人一般会这么回复
2011-08-22 17:48 | 过路客

# re: 基础排序查找算法[未登录]  回复  更多评论   

@过路客
除了考试这种二分查找哪里用上了,我见识短浅,拜托您举个例子吧:-)

当随机查找一个值时通常用哈希,不需要二分查找,因为二分查找跟哈希比起来慢多了,如果各个元素之间需要保持相对顺序的话(假设可能有重复的),通常是查找上界或下界,用的是楼主这个二分查找的变形版本(看看STL lower_bound和upper_bound以及equal_range),而这个既非找上界也非找下界的二分查找在实际应用中几乎就是个废物!
2011-08-25 13:24 | Chipset

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理