| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 449 人关注过本帖
标题:在数据结构与算法上看到的排序代码,求大神解释。
只看楼主 加入收藏
南国雨
Rank: 1
等 级:新手上路
帖 子:26
专家分:9
注 册:2015-2-1
结帖率:72.73%
收藏
已结贴  问题点数:20 回复次数:7 
在数据结构与算法上看到的排序代码,求大神解释。
程序代码:
void Direct_Insert_sort(DataType R[],int n){
    for(i=2;i<=n;++i){
        if(R[i].key<R[i-1].key){
            R[0]=R[i];
    for(j=i-1;R[0].key<R[j].key;j--){
        R[j+1]=R[j];
    }
        R[j+1]=R[0];
        }
    }
}

我敲了一遍,又加了个主函数,可是始终都无法排列正确。
求大神:
1.补个主函数
2.然后来个正解。
3.如果能对这个函数解释一下,那就更好了!
4.还有 R[]必须是一个结构体吗?
2015-03-07 13:29
诸葛欧阳
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:流年
等 级:贵宾
威 望:82
帖 子:2790
专家分:14619
注 册:2014-10-16
收藏
得分:0 
你还要定义一个DateType类型结构体

一片落叶掉进了回忆的流年。
2015-03-07 16:15
南国雨
Rank: 1
等 级:新手上路
帖 子:26
专家分:9
注 册:2015-2-1
收藏
得分:0 
回复 2楼 诸葛欧阳
为什么非要定义结构体呢?
如果定义的话,该怎么定义。
typedef{
   int key;
}R[5];
像这样定义吗?
2015-03-07 18:25
风车转风车89
Rank: 2
等 级:论坛游民
帖 子:125
专家分:45
注 册:2014-9-15
收藏
得分:0 
应该是插入排序,typedef struct{ int key;}DateType; DateType R[5];
2015-03-08 12:37
南国雨
Rank: 1
等 级:新手上路
帖 子:26
专家分:9
注 册:2015-2-1
收藏
得分:0 
回复 4楼 风车转风车89
说的也些道理哦。
但是我不理解的是,为什么要用结构题呢?
更何况结构体里面只有一个int型
2015-03-09 21:23
ck018
Rank: 2
等 级:论坛游民
帖 子:6
专家分:34
注 册:2015-2-26
收藏
得分:20 
/*
功能:外层for循环从1到n对i进行计数。在每一步中,元素v[0]到v[i-1]
      已经排好顺序,元素v[i]到v[n-1]仍然有待排序。内层的循环从
      i-1开始对j进行倒数,一次移动一个数组元素,直到直到v[i]需要
      插入的正确位置,所以这个算法称为插入排序算法。
      对于非常庞大的未排序数组,这个算法效率低下。
      这种排序算法的时间复杂度为n*n即(O(n^2))。
*/

void intsertsort(int v[], int n)
{
    register int i, j, temp;
    for (i = 1; i < n; i++)
    {
        temp = v[i];
        for (j = i - 1; j >= 0 && v[j] > temp; j--)
        {
            v[j+1] = v[j];
            v[j+1] = temp;
        }
    }
}
2015-03-09 22:05
ck018
Rank: 2
等 级:论坛游民
帖 子:6
专家分:34
注 册:2015-2-26
收藏
得分:0 
/*
功能:Shell排序算法
思路:对整型数组进行排序的Shell排序算法。 Shell排序算法是D. L. Shell
    于1959年发明的,其基本思想是:先比较距离远的元素,而不是像简单交
    换排序算法那样先比较相邻的元素。这样可以快速减少大量的无序情况
    ,从而减轻后续的工作。被比较的元素之间的距离逐步减少,直到减少
    为1, 这时排序变成了相邻元素的互换。
    该函数中包含一个三重嵌套的for循环语句。最外层的for语句控制两个被
    比较元素之间的距离,从len/2开始,逐步进行对折,直到距离为0。巾问层
    的for循环语句用于在元素间移动位置。最内层的for语句用于比较各对相
    距gap个位置的元素,当这两个元素逆序时把它们互换过来。 山于gap的值
    最终要递减到1 ,因此所有元素最终都会位于正确的排序位置上。 注意,
    即使最外层for循环的控制变址不是算术级数,for语句的书写形式仍然没
    有变,这就说明for语句具有很强的通用性。
{9, 8, 7, 6, 5, 4, 3, 2, 1};未排序状态
{1, 4, 3, 2, 5, 8, 7, 6, 9};len/2 1次,i从len/2到len-1,j从0到len/2 隔4两两1组 gap=len/2
{1, 2, 3, 4, 5, 6, 7, 8, 9};len/2 2次,i从len/4到len-1,j从0到len/4 隔2两两1组 gap=len/4
{1, 2, 3, 4, 5, 6, 7, 8, 9};len/2 3次,i从len/8到len-1,j从0到len/8 隔1两两1组 gap=len/8
作者:Ck018
时间:2015.1.27
修改:
*/

# include<stdio.h>
# include<stdlib.h>

void shell_sort(int src[], int len);

int main(int agrc, char* agrv[])
{
    int i;
    int src[] = {9, 7, 8, 6, 1, 4, 3, 2, 5};
    shell_sort(src, 9);
    for (i=0; i<9; i++)
        printf("%d", src[i]);

    system("pause");
    return 0;
}

void shell_sort(int src[], int len)
{
    int gap, i, j, temp;

    for (gap=len/2; gap>=1; gap/=2)
        for (i=gap; i<len; i++)
            for (j=i-gap; j>=0 && src[j]>src[j+gap]; j-=gap)
            {
                temp = src[j];
                src[j] = src[j+gap];
                src[j+gap] = temp;
            }
}
2015-03-09 22:08
ck018
Rank: 2
等 级:论坛游民
帖 子:6
专家分:34
注 册:2015-2-26
收藏
得分:0 
/*
功能:
     只要简单地在前两个循环的外面包装第3个循环,在insertsort函数
     使用常量1的几个地方引入gap(两个相比较数组元素之间的距离),
     可以把插入排序算法的效率从O(n^2)提高到O(n^1.25)。
     下面的算法与shell排序算法相似。但是这里我们
     对他进行修改,提高算法速度。
*/

void shellsort(register int v[], int n)
{
    register int gap, i, j ,temp;
    gap = 1;
    do (gap = 3*gap + 1) while (gap <= n);
    for (gap /= 3; gap > 0; gap /= 3)
    {
        for (i = gap; i < n; i++)
        {
            temp = v[i];
            for (j=i-gap; (j>=0) && (v[j])>temp; j-=gap)
            {
                v[j+gap] = v[j];
                v[j+gap] = temp;
            }
        }
    }
}

/*
算法优化:改进之处在于:1在原来的shell函数中,gap的值从n/2开始,
          每次在外层循环中除以2.在这个版本中,gap被初始化为
      (1,4,13,40,121,....)这个序列中不大于n的最大值,并且
      每次进过外层循环时,gap的值被除以3.这个改进使这个算法的
      速度提高了20% ~ 30%(gap初始值的这种选择方法证明比使用
      n作为初始值更为优越)。2内层循环中的赋值从3个减少到1个。
      3增加了register和void储存类别。在有点的编译器中能提高效率。
*/
2015-03-09 22:11
快速回复:在数据结构与算法上看到的排序代码,求大神解释。
数据加载中...
 
   



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

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