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

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-04-30 23:14:57

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

二、算法思想
        直接插入排序的基本思想是:每一趟将一个待排序的记录,按其关键字值的大小插入到已经排序的部分文件中适当位置上,直到全部插入完成。
        假设记录存放在r[1, n]之中,r[1, i-1]是已排好序的记录;r[i-1, n]是没排序的记录。插入排序把未排序记录中的r[i]插入到r[1, i-1]之中,使r[1, i]成为有序,r[i]的插入过程就是完成排序中的一趟。随着有序区的不断扩大,使r[1, n]全部有序。

三、程序实现
        实现直接插入排序的函数如下:
        void insertsort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j;
            for (i=2; i<=n; i++)
            {
                r[0] = r[i];                        // r[0]是监视哨
                j = i - 1;
                while (r[0].key < r[j].key)    // 进行元素移动,以便腾出一个位置插入r[i]
                {
                    r[j+1] = r[j];
                    j--;
                }
                r[j+1] = r[0];                    // 在j+1位置处插入r[0]
            }
        }
        当原始记录已按关键字递增有序排列,即为正序时,呈现最佳状态,整个排序过程总的比较次数为n-1次,记录中移动次数为2(n-1);反之,原始记录逆序时,呈现最坏状态,整个排序过程总的比较次数为(n+2)(n-1)/2,总的移动次数为(n+4)(n-1)/2,。插入排序算法的时间复杂度是O(n2),它是一种稳定的排序方法。




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