宠辱不惊,看庭前花开花落;去留无意,望天空云卷云舒

发布新日志

  • 排序或分类

    2008-01-14 16:39:21

      所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下:
      输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn
      输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

    1.被排序对象--文件
      被排序的对象--文件由一组记录组成。
      记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)。
      注意:
         在不易产生混淆时,将关键字项简称为关键字。

    2.排序运算的依据--关键字
         用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。
         关键字的选取应根据问题的要求而定。
    【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用"准考证号"作为关键字。若要按照考生的总分数排名次,则需用"总分数"作为关键字。

    排序的稳定性

         当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。
         在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的
      注意:
         排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。

    排序方法的分类

    1.按是否涉及数据的内、外存交换分

         在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序
      注意:
         ① 内排序适用于记录个数不很多的小文件
         ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。

    2.按策略划分内部排序方法
         可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。

    插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
         本节介绍两种插入排序方法:直接插入排序和希尔排序。

    直接插入排序基本思想

    1、基本思想

         假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。

    2、第i-1趟直接插入排序:
         通常将一个记录R[i](i=2,3,…,n-1)插入到当前的有序区,使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。
         排序过程的某一中间时刻,R被划分成两个子区间R[1..i-1](已排好序的有序区)和R[i..n](当前未排序的部分,可称无序区)。
         直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1..i-1]中适当的位置上,使R[1..i]变为新的有序区。因为这种方法每次使有序区增加1个记录,通常称增量法。
         插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理,此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置,须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

    一趟直接插入排序方法

    1.简单方法

         首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置,腾出k位置上的空间插入R[i]。
      注意:
         若R[i]的关键字大于等于R[1..i-1]中所有记录的关键字,则R[i]就是插入原位置。

    2.改进的方法
      一种查找比较操作和记录移动操作交替地进行的方法。
    具体做法:
         将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1,i-2,…,1)的关键字进行比较:
         ① 若R[j]的关键字大于R[i]的关键字,则将R[j]后移一个位置;
          ②若R[j]的关键字小于或等于R[i]的关键字,则查找过程结束,j+1即为R[i]的插入位置。
         关键字比R[i]的关键字大的记录均已后移,所以j+1的位置已经腾空,只要将R[i]直接插入此位置即可完成一趟直接插入排序。

    直接插入排序算法

    1.算法描述

      void lnsertSort(SeqList R)
       { //对顺序表R中的记录R[1..n]按递增序进行插入排序
        int i,j;
        for(i=2;i<=n;i++) //依次插入R[2],…,R[n]
          if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys,则R[i]
                                  //应在原有位置上
            R[0]=R[i];j=i-1; //R[0]是哨兵,且是R[i]的副本
            do{ //从右向左在有序区R[1..i-1]中查找R[i]的插入位置
             R[j+1]=R[j]; //将关键字大于R[i].key的记录后移
             j-- ;
             }while(R[0].key<R[j].key); //当R[i].key≥R[j].key时终止
            R[j+1]=R[0]; //R[i]插入到正确的位置上
           }//endif
       }//InsertSort

    交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
         应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。

    冒泡排序

    1、排序方法

         将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
    (1)初始
         R[1..n]为无序区。

    (2)第一趟扫描
         从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key<R[j].key,则交换R[j+1]和R[j]的内容。
         第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。

    (3)第二趟扫描

         扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……
         最后,经过n-1 趟扫描可得到有序区R[1..n]
      注意:
         第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。

    2、冒泡排序过程示例
         对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【参见动画演示

    3、排序算法
    (1)分析
         因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。
         若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。

    (2)具体算法

      void BubbleSort(SeqList R)
       { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序
         int i,j;
         Boolean exchange; //交换标志
         for(i=1;i<n;i++){ //最多做n-1趟排序
           exchange=FALSE; //本趟排序开始前,交换标志应为假
           for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描
            if(R[j+1].key<R[j].key){//交换记录
              R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元
              R[j+1]=R[j];
              R[j]=R[0];
              exchange=TRUE; //发生了交换,故将交换标志置为真
             }
           if(!exchange) //本趟排序未发生交换,提前终止算法
                 return;
         } //endfor(外循环)
        } //BubbleSort

  • 算法效率的度量

    2008-01-14 16:36:24

    算法效率的度量

    算法执行时间需过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常常有两种方法:

    1、事后统计的方法。因为很多计算机内部都有计时功能,有的甚至可精确到毫秒及,不同算法的程序可通过一组或若干组相同的统计数据以分辨优劣。但这种方法有两个缺陷:一是必须先运行依据算法编制的程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优劣。因此人们常常采用另一种事前分析估算的方法。

    2、事前分析估算的方法。一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:a依据的算法选用何种策略。b问题的规模,例如求100内还是1000内的素数。c书写程序的语言,对于同一个算法,实现语言的级别越高,执行效率就越底。e机器执行指令的速度。

    一个算法是由控制结构(顺序、分支和循环三种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法,通常的做法是,从算法中选取一种对于所研究的问题平说是基本操作的原操用,以该基本操作重复执行的次数做为算法的时间量度。

Open Toolbar