Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4510460
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-05-01 10:52:26

一、数据结构
        约定排序均为升序排序,要排序的记录存储在线性表中,线性表由排序关键字和其它域组成,其定义如下:
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型,比如int,float或char等,在算法中,约定其为int类型。

二、算法思想
        冒泡排序的基本思想是:通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。整个算法是从最下面的记录开始,对每两个相邻的关键进行比较,且使关键字较小的记录换至关键字较大的记录之上,使得经过一趟起泡排序后,关键字最小的记录到达最上端,接着,再在剩下的记录中找关键字最小的记录,并把它换在第二个位置上。依次类推,一直到所有记录都有序为止。

三、程序实现
        实现冒泡排序的函数如下:
        void bubblesort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j;
            struct rec w;
            for (i=1; i<=n-1; i++)
            {
                for (j=n; j>i+1; j--)
                {
                    if (r[j].key < r[j-1].key)    // 比较
                    {                                  // r[j]与r[j-1]进行交换
                        w = r[j];
                        r[j] = r[j-1];
                        r[j-1] = w;
                    }
                }
            }
        }
        冒泡排序算法的时间复杂度是O(n2),它是一种稳定的排序方法。




阅读(1638) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

scq2099yt2013-05-01 10:52:39

文明上网,理性发言...