服务器之家

服务器之家 > 正文

解析shell排序的实现代码

时间:2020-12-01 15:08     来源/作者:脚本之家

复制代码 代码如下:


#include <iostream>
using namespace std;
void ShellQin(int A[],int n)
{
    int gap=n/2;
    int i,j;
    for(;gap>0;gap=gap/2)//设置初始gap,按照gap进行分组,gap按照gap/2递减
    {
        //设置好gap以后,从gap开始一直到最后一个元素,为每一个元素在其对应的组进行插入排序。gap应该是该组所在位置的第2个元素,第一个元素位置是0
        for(i=gap;i<n;i++)
        {
            j=i;
            //对一组进行插入排序
            if(A[j-gap]>A[j])
            {
                /*如果A[j]>A[j-gap]意味着A[j]大于其所在组的前一个位置,那么将
                  A[j]保存在temp中,将从组中所有大于A[j]的数后移,最后空出来的位置
                  存放A[j]
                */
                int temp=A[j];//保存A[J]
                do
                {
                    A[j]=A[j-gap];
                    j=j-gap;
                }while(j>=0&&temp<A[j]);//后移每一个大于A[j]的数
                A[j+gap]=temp;//将A[j]插入到合适的位置
            }
        }
    }
    for(i=0;i<n;i++)
    {
        cout<<*(A+i)<<" ";
    }
}
int main1()
{
    int a[]= {5,4,3,21,1,100,93,1,3,2,4};
    ShellQin(a,11);
    return 0;
}


和朋友讨论过后,虽然希尔和插排最坏的情况都是n平方,认为希尔效率要比插排好的原因是,时间复杂度前面的系数要小于插排,特别是逆序的时候,很明显的减少了比较的次数。就如同快排之于堆排,快排前的系数远小于堆排,加上简单易用所以称为程序员们最爱。
下面的这种算法也叫做shell排序,与上面的区别在于进行插入排序的时候用交换相邻两个数据代替了移位(即先取出key关键字,将大于key的值向后移位)

复制代码 代码如下:


//交换两个小数
void swapdouble(double *a,double *b){
   double temp=*a;
   *a=*b;
   *b=temp;
}
void Shell(double* p,int n)
{
    int gap=n/2;
    int i,j;
    for(;gap>0;gap=gap/2)
    {
        for(i=gap;i<=n-1;i++)//从gap开始为所在的每个组进行插入排序,i=gap是该组的第二个元素
        {
            j=i;
            if(*(p+j)<*(p+j-gap))
            {
                while(j>=gap && *(p+j)<*(p+j-gap))
                {
                    swapdouble(p+j,p+j-gap);
                    j=j-gap;
                }
            }
        }
    }
}

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部