10.26.c

来自「数据结构习题及答案」· C语言 代码 · 共 47 行

10.26②  如下所述改写教科书1.4.3节中的起泡排序算法：
将算法中用以起控制作用的布尔变量change改为一个整型变
量，指示每一趟排序中进行交换的最后一个记录的位置，并
以它作为下一趟起泡排序循环终止的控制值。

实现下列函数：
void BubbleSort(SqList &L);
/* 元素比较和交换必须调用以下比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"  */
/* Status GT(RedType a, RedType b);   比较：">"  */
/* void Swap(RedType &a, RedType &b); 交换       */

顺序表的类型SqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RedType;

typedef struct {
   RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
   int     length;
} SqList;

比较函数和交换函数:
Status LT(RedType a, RedType b);   // 比较函数："<"
Status GT(RedType a, RedType b);   // 比较函数：">"
void Swap(RedType &a, RedType &b); // 交换函数
void BubbleSort(SqList &L)
/* 元素比较和交换必须调用如下定义的比较函数和交换函数：*/
/* Status LT(RedType a, RedType b);   比较："<"        */
/* Status GT(RedType a, RedType b);   比较：">"        */
/* void Swap(RedType &a, RedType &b); 交换             */
{ 
 int last,i;
 int change=L.length;
 while(change!=1)
   {
     for(last=1,i=1;i<change;i++)
         if(GT(L.r[i],L.r[i+1]))
           {Swap(L.r[i],L.r[i+1]);
            last=i;
             }           
    change=last;
    }   
}