| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 10439 人关注过本帖
标题:对同一列数据用各种排序法来统计分别各自交换了多少次,来比较用哪种方法交 ...
只看楼主 加入收藏
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:0 
用“插入排序法”写好了,排序顺序和上面的不一样,但是交换次数一样。都是45次。
程序代码:
#include<stdio.h>
#include<malloc.h>
void InsertSorting(int a[],int len)
{   int count=0;
    for(int i=1;i<len;i++)
    {
        int k=i,z;
        int temp=a[k];
        for(int j=i-1;(j>=0)&&(a[j]>temp);j--)
        {
            a[j+1]=a[j];
            k=j;
        a[k]=temp;
        printf(" 第 %3d 次交换: ",++count);
        for(z=0;z<10;z++)
              printf("%4d ",a[z]);
         printf("\n");
         }
        
    }
    printf("共交换%4d 次",count);
}
int main(int argc, char *argv[])
{
   int a[10]={10,9,8,7,6,5,4,3,2,1};
   int i=0;
   printf("这段代码是用插入排序法来统计共交换了多少次。\n ");
   printf("交换前的数据: ");
    for(i=0;i<10;i++)
              printf(" %4d",a[i]);
    printf("\n");
   InsertSorting(a,10);
   printf(" 交换后的数据: ");
   for(i=0;i<10;i++)
             printf("%3d ",a[i]);
  return 0;
}

效果图:
图片附件: 游客没有浏览图片的权限,请 登录注册
2018-05-22 21:53
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:5 
回复 11楼 自学的数学
编程论坛 - 各种插入排序算法小结

https://bbs.bccn.net/viewthread.php?tid=435801&highlight=%B2%E5%C8%EB%C5%C5%D0%F2

关于插入排序可以看看这个~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-22 22:08
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:0 
回复 12楼 九转星河
不错的文章,我准备对文中提到的各种排序方法都来试试,比较一番,是不是还是45呢。
2018-05-22 22:25
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:0 
回复 8楼 九转星河
插入,快排和归并
都是交换排序的
不知道什么是赋值排序 你想说分配排序??

https://zh.
2018-05-22 22:26
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 14楼 lin5161678
其实实质理解成交换排序也没有错,只是交换不是只有t=a;a=b;b=t;这种表达形式,分配额外空间的通常就不是那种形式的了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-22 22:28
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:0 
回复 14楼 lin5161678
分配排序分为:桶排序和基数排序。
   桶排序和基数排序均属于分配排序。分配排序的基本思想:排序过程无须比较关键字,而是通过用额外的空间来"分配"和"收集"来实现排序,它们的时间复杂度可达到线性阶:O(n)。简言之就是:用空间换时间,所以性能与基于比较的排序才有数量级的提高!
    桶排序所需要的额外空间取决于关键字的个数,若 array[0..n - 1] 中关键字的取值范围是 0 到 m - 1 的整数,则必须设置 m 个箱子。因此箱排序要求关键字的类型是有限类型,否则可能要无限个箱子。一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的,故箱子的类型应设计成链表为宜。
   基数排序基本思想:基数排序是对桶排序的改进和推广。如果说桶排序是一维的基于桶的排序,那么基数排序就是多维的基于桶的排序。我这么说,可能还不是太清楚。比方说:用桶排序对 [0, 30] 之间的数进行排序,那么需要 31 个桶,分配一次,收集一次,完成排序;那么基数排序则只需要 0 - 9 总共 10 个桶(即关键字为数字 0 - 9),依次进行个位和十位的分配和收集从而完成排序。
2018-05-22 22:36
lin5161678
Rank: 12Rank: 12Rank: 12
等 级:贵宾
威 望:45
帖 子:1136
专家分:3729
注 册:2011-12-3
收藏
得分:5 
回复 15楼 九转星河
既然提到额外空间
那么你应该是想说分配排序了
插入 快排 归并这些不是分配排序
虽然归并有辅助空间
但是这些排序是基于比较 进行排序的
交换操作怎么写倒比较次要
基于比较的排序 和 分配排序 主要区别是
一个排序依赖比较 时间复杂度在理论上的下限是O(n*log(n))
分配排序不依赖比较 时间复杂度可以达到O(n)

https://zh.
2018-05-22 22:50
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:5 
答主显然没有正真完全吃透各种排序算法,我也没有,但我知道选择法排序交换数据最多只需要交换n-1次数据,像题主这种倒序变顺序只需要交换n/2次数据即可,即交换5次,最糟糕的数据为“a[]={2,3,5,7,9,10,8,6,4,1}”,这样交换9次,代码如下:
程序代码:
#include<stdio.h>
void print(int *a,int c)
{
    int i;
    printf("第%d次:",c);
    for(i=0;i<10;i++)printf("%3d",a[i]);
    printf("\n");
}
void main()
{
    int i,j,k,l=0,a[]={10,9,8,7,6,5,4,3,2,1};
    for(i=0;i<9;i++)
    {
        k=i;
        for(j=i+1;j<10;j++)if(a[k]>a[j])k=j;
        if(k!=i)
        {
            a[k]^=a[i];
            a[i]^=a[k];
            a[k]^=a[i];
            print(a,++l);
        }
    }
}


其实排序效率不仅仅在数据交换上,还有遍历数据集合的效率,有的算法还针对不同的数据结构,比如插入排序在链表排序中效率就很高。

[此贴子已经被作者于2018-5-22 23:00编辑过]

2018-05-22 22:51
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 17楼 lin5161678
对哦,可以看比较次数而不是交换次数,这就直接多了~

[此贴子已经被作者于2018-5-22 23:01编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-22 22:59
自学的数学
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:贵宾
威 望:46
帖 子:967
专家分:4146
注 册:2017-11-15
收藏
得分:0 
回复 19楼 九转星河
你说:"可以看比较次数"。那么就以下面的冒泡排序法为例,如何查看呢??
程序代码:
#include <stdio.h>

 void sort(int *a,int len)

 {
   int i=0;
   int j;
   int t;
   for(i=0;i<len-1;i++)  
     {
       for(j=0;j<len-i-1;j++)
          {
           if(a[j]>a[j+1])
              {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
             }
          }
    }
  }
int main(int argc, char *argv[])
{
   int a[10]={10,9,8,7,6,5,4,3,2,1};
   int i=0;
   sort(a,10);
   for(i=0;i<10;i++)
             printf("%d ",a[i]);
  return 0;
}


[此贴子已经被作者于2018-5-23 09:50编辑过]

2018-05-23 09:29
快速回复:对同一列数据用各种排序法来统计分别各自交换了多少次,来比较用哪种方 ...
数据加载中...
 
   



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

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