| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 624 人关注过本帖
标题:插入排序的优化问题,这个是用最简单的从后向前挨个比较的,是否可以用折半 ...
只看楼主 加入收藏
一条沙丁鱼
Rank: 1
等 级:新手上路
威 望:1
帖 子:44
专家分:7
注 册:2015-4-5
结帖率:100%
收藏
已结贴  问题点数:15 回复次数:6 
插入排序的优化问题,这个是用最简单的从后向前挨个比较的,是否可以用折半查找来寻找新元素添加的位置
#include<iostream>
using namespace std;
 
void insert_sort(int a[],int n)
{
 int i,j,temp;
 for(i=1;i<n;i++)
 {  
  temp=a[i];  
  for(j=i-1;j>=0 && temp<a[j];j--)
  {   
   a[j+1]=a[j];  
  }  
  a[j+1]=temp;
 }
}
  
void print_arry(int a[], int len)
{
 for(int i=0;i<len;i++)
 {  
  cout<<a[i]<<" ";
 }
 cout<<endl;
}
 
void main()
{
 int n,i;
 int a[50];
 cout<<"请输入要排序数的个数:"<<endl;
 cin>>n;
 cout<<"请输入要排序的数:"<<endl;
 for(i=0;i<n;i++)
 {
  cin>>a[i];
 }
 cout<<endl;
 cout<<"排序前为:"<<endl;
 print_arry(a,n);
 insert_sort(a,n);
 cout<<"排序后为:";  
 print_arry(a,n);
}
搜索更多相关主题的帖子: include 元素 
2015-05-17 17:31
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:2 
当然可以

一片落叶掉进了回忆的流年。
2015-05-17 21:22
一条沙丁鱼
Rank: 1
等 级:新手上路
威 望:1
帖 子:44
专家分:7
注 册:2015-4-5
收藏
得分:0 
回复 2楼 诸葛欧阳
请问,可以给出用折半查找的代码吗?
2015-05-20 13:49
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:3 
折半查找 的C标准库函数是 bsearch,需要#include <stdlib.h>
折半查找 的C++标准库函数是 std::binary_search,需要#include <algorithm>
但,你要想想,折半查找对你的这段代码有没有用?
2015-05-20 15:46
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:2 
说错了,std::binary_search 是傻屄函数,只会返回是否存在,应当用 std::upper_bound
2015-05-20 15:53
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:8 
对折插入,根据字面理解用递归做了个,不知道理解错了没有,代码如下(只擅长c代码):
程序代码:
#include <stdio.h>
void halfinsert(int *p,int num,int len,int l,int r)
{//折半插入 p已排序好的带插入数组,num待插入的数据,len当前未插入数据的数组所含数据个数,l对折左边数组下标,r对折右边数组下标
    int i,j;
    if((r-l)<2)
    {
        j=r;   //中间插入位置
        if(num<p[l])j=l;   //最左边的插入位置
        if(num>p[r])j=r+1;   //最右边的插入位置
        for(i=len-1;i>=j;i--)p[i+1]=p[i];   //如果插入的数据在原数组中间,则右移插入位置右边的所有数据
        p[j]=num;   //插入数据
        return;
    }
    i=l+(r-l+1)/2; 
    if(p[i]>num)
        halfinsert(p,num,len,l,i);   //折半插入左边
    else
        halfinsert(p,num,len,i,r);   //折半插入右边
}
void main()
{
    int i,a[10]={25,30,35,40,45,50,55,60};   //已排序好的原数据,注意数组长度为10,当前只有8个数据
    halfinsert(a,38,8,0,7);     //对折插入数据38
    for(i=0;i<9;i++)printf("%4d",a[i]);
    printf("\n");
}


 

[ 本帖最后由 wmf2014 于 2015-5-20 21:44 编辑 ]

能编个毛线衣吗?
2015-05-20 21:36
一条沙丁鱼
Rank: 1
等 级:新手上路
威 望:1
帖 子:44
专家分:7
注 册:2015-4-5
收藏
得分:0 
回复 6楼 wmf2014
好的,谢谢大神
2015-05-23 20:54
快速回复:插入排序的优化问题,这个是用最简单的从后向前挨个比较的,是否可以用 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.047628 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved