第十章　内部排序　题解

　　　　　　　　　　　　　　　　　第十章 内部排序
10.23
void Insert_Sort1(SqList &L)/*监视哨设在高下标端的插入排序算法
{
  k=L.length;
  for(i=k-1;i;--i) /*从后向前逐个插入排序
    if(L.r[i].key>L.r[i+1].key)
    {
      L.r[k+1].key=L.r[i].key; /*监视哨
      for(j=i+1;L.r[j].key>L.r[i].key;++j)
        L.r[j-1].key=L.r[j].key; /*前移
      L.r[j-1].key=L.r[k+1].key; /*插入
    }
}/*Insert_Sort1
10.24
void BiInsert_Sort(SqList &L)/*二路插入排序的算法
{
  int d[MAXSIZE]; /*辅助存储
  x=L.r .key;d =x;
  first=1;final=1;
  for(i=2;i<=L.length;i++)
  {
    if(L.r[i].key>=x) /*插入前部
    {
      for(j=final;d[j]>L.r[i].key;j--)
        d[j+1]=d[j];
      d[j+1]=L.r[i].key;
      final++;
    }
    else /*插入后部
    {
      for(j=first;d[j]<L.r[i].key;j++)
        d[j-1]=d[j];
      d[(j-2)%MAXSIZE+1]=L.r[i].key;
      first=(first-2)%MAXSIZE+1; /*这种形式的表达式是为了兼顾first=1的情况
    }
  }/*for
  for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)/*将序列复制回去
    L.r[j].key=d[i];
}/*BiInsert_Sort
10.25
void SLInsert_Sort(SLList &L)/*静态链表的插入排序算法
{
  L.r[0].key=0;L.r[0].next=1;
  L.r[1].next=0; /*建初始循环链表
  for(i=2;i<=L.length;i++) /*逐个插入
  {
    p=0;x=L.r[i].key;
    while(L.r[L.r[p].next].key<x&&L.r[p].next)
      p=L.r[p].next;
    q=L.r[p].next;
    L.r[p].next=i;
    L.r[i].next=q;
  }/*for
  p=L.r[0].next;
  for(i=1;i<L.length;i++) /*重排记录的位置
  {
    while(p<i) p=L.r[p].next;
    q=L.r[p].next;
    if(p!=i)
    {
      L.r[p]<->L.r[i];
      L.r[i].next=p;
    }
    p=q;
  }/*for
}/*SLInsert_Sort
10.26
void Bubble_Sort1(int a[ ],int n)/*对包含n个元素的数组a进行改进的冒泡排序
{
  change=n-1; /*change指示上一趟冒泡中最后发生交换的元素
  while(change)
  {
    for(c=0,i=0;i<change;i++)
      if(a[i]>a[i+1])
      {
        a[i]<->a[i+1];
        c=i+1; /*c指示这一趟冒泡中发生交换的元素
      }
    change=c;
  }/*while
}/*Bubble_Sort1
10.27
void Bubble_Sort2(int a[ ],int n)/*相邻两趟是反方向起泡的冒泡排序算法
{
  low=0;high=n-1; /*冒泡的上下界
  change=1;
  while(low<high&&change)
  {
    change=0;
    for(i=low;i<high;i++) /*从上向下起泡
      if(a[i]>a[i+1])
      {
        a[i]<->a[i+1];
        change=1;
      }
    high--; /*修改上界
    for(i=high;i>low;i--) /*从下向上起泡
      if(a[i]<a[i-1])
      {
        a[i]<->a[i-1];
        change=1;
      }
    low++; /*修改下界
  }/*while
}/*Bubble_Sort2
10.28
void Bubble_Sort3(int a[ ],int n)/*对上一题的算法进行化简,循环体中只包含一次冒泡
{
  int b[ 3 ]; /*b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
  d=1;b[0]=0;b[ 2 ]=n-1; /*d为冒泡方向的标识,1为向上,-1为向下
  change=1;
  while(b[0]<b[ 2 ]&&change)
  {
    change=0;
    for(i=b[1-d];i!=b[1+d];i+=d) /*统一的冒泡算法
      if((a[i]-a[i+d])*d>0) /*注重这个交换条件
      {
        a[i]<->a[i+d];
        change=1;
      }
    b[1+d]-=d; /*修改边界
    d*=-1; /*换个方向
  }/*while
}/*Bubble_Sort3
10.29
void OE_Sort(int a[ ],int n)/*奇偶交换排序的算法
{
  change=1;
  while(change)
  {
    change=0;
    for(i=1;i<n-1;i+=2) /*对所有奇数进行一趟比较
      if(a[i]>a[i+1])
      {
        a[i]<->a[i+1];
        change=1;
      }
    for(i=0;i<n-1;i+=2) /*对所有偶数进行一趟比较
      if(a[i]>a[i+1])
      {
        a[i]<->a[i+1];
        change=1;
      }
  }/*while
}/*OE_Sort
分析:本算法的结束条件是连续两趟比较无交换发生
10.30
typedef struct {
                     int low;
                     int high;
                   } boundary; /*子序列的上下界类型
void QSort_NotRecurve(int SQList &L)/*快速排序的非递归算法
{
  low=1;high=L.length;
  InitStack(S); /*S的元素为boundary类型
  while(low<high&&!StackEmpty(S)) /*注重排序结束的条件
  {
    if(high-low>2) /*假如当前子序列长度大于3且尚未排好序
    {
      pivot=Partition(L,low,high); /*进行一趟划分
      if(high-pivot>pivot-low)
      {
        Push(S,{pivot+1,high}); /*把长的子序列边界入栈
        high=pivot-1; /*短的子序列留待下次排序
      }
      else
      {
        Push(S,{low,pivot-1});
        low=pivot+1;
      }
    }/*if
    else if(low<high&&high-low<3)/*假如当前子序列长度小于3且尚未排好序
    {
      Easy_Sort(L,low,high); /*直接进行比较排序
      low=high; /*当前子序列标志为已排好序
    }
    else /*假如当前子序列已排好序但栈中还有未排序的子序列
    {
      Pop(S,a); /*从栈中取出一个子序列
      low=a.low;
      high=a.high;
    }
  }/*while
}/*QSort_NotRecurve
int Partition(SQList &L,int low,int high)/*一趟划分的算法,与书上相同
{
  L.r[0]=L.r[low];
  pivotkey=L.r[low].key;
  while(low<high)
  {
    while(low<high&&L.r[high].key>=pivotkey)
      high--;
    L.r[low]=L.r[high];
    while(low<high&&L.r[low].key<=pivotkey)
      low++;
    L.r[high]=L.r[low];
  }/*while
  L.r[low]=L.r[0];
  return low;
}/*Partition
void Easy_Sort(SQList &L,int low,int high)/*对长度小于3的子序列进行比较排序
{
  if(high-low==1) /*子序列只含两个元素
    if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];
  else /*子序列含有三个元素
  {
    if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
    if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];
    if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
  }
}/*Easy_Sort
10.31
void Divide(int a[ ],int n)/*把数组a中所有值为负的记录调到非负的记录之前
{
  low=0;high=n-1;
  while(low<high)
  {
    while(low<high&&a[high]>=0) high--; /*以0作为虚拟的枢轴记录
    a[low]<->a[high];
    while(low<high&&a[low]<0) low++;
    a[low]<->a[high];
  }
}/*Divide
10.32
typedef enum {RED,WHITE,BLUE} color; /*三种颜色
void Flag_Arrange(color a[ ],int n)/*把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列
{
  i=0;j=0;k=n-1;
  while(j<=k)
    switch(a[j])
    {
      case RED:
        a[i]<->a[j];
        i++;
        j++;
        break;
      case WHITE:
        j++;
        break;
      case BLUE:
        a[j]<->a[k];
        k--; /*这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况
    }
}/*Flag_Arrange
分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.
10.33
void LinkedList_Select_Sor t(LinkedList &L)/*单链表上的简单选择排序算法
{
  for(p=L;p->next->next;p=p->next)
  {
    q=p->next;x=q->data;
    for(r=q,s=q;r->next;r=r->next) /*在q后面寻找元素值最小的结点
      if(r->next->data<x)
      {
        x=r->next->data;
        s=r;
      }
    if(s!=q) /*找到了值比q->data更小的最小结点s->next
    {
      p->next=s->next;s->next=q;
      t=q->next;q->next=p->next->next;
      p->next->next=t;
    } /*交换q和s->next两个结点
  }/*for
}/*LinkedList_Select_Sort
10.34
void Build_Heap(Heap &H,int n)/*从低下标到高下标逐个插入建堆的算法
{
  for(i=2;i<n;i++)
  { /*此时从H.r[1]到H.r[i-1]已经是大顶堆
    j=i;
    while(j!=1) /*把H.r[i]插入
    {
      k=j/2;
      if(H.r[j].key>H.r[k].key)
        H.r[j]<->H.r[k];
      j=k;
    }
  }/*for
}/*Build_Heap
10.35
void TriHeap_Sort(Heap &H)/*利用三叉树形式的堆进行排序的算法
{
  for(i=H.length/3;i>0;i--)
    Heap_Adjust(H,i,H.length);
  for(i=H.length;i>1;i--)
  {
    H.r[1]<->H.r[i];
    Heap_Adjust(H,1,i-1);
  }
}/*TriHeap_Sort
void Heap_Adjust(Heap &H,int s,int m)/*顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆
{
  rc=H.r[s];
  for(j=3*s-1;j<=m;j=3*j-1)
  {
    if(j<m&&H.r[j].key<H.r[j+1].key) j++;
    if(j<m&&H.r[j].key<H.r[j+1].key) j++;
    H.r[s]=H.r[j];
    s=j;
  }
  H.r[s]=rc;
}/*Heap_Adjust
分析:本算法与课本上的堆排序算法相比,只有两处改动:1.建初始堆时,i的上限从H.length/3开始(为什么?) 2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最左边的孩子的序号的计算公式为j=3*s-1(为什么?)
10.36
void Merge_Sort(int a[ ],int n)/*归并排序的非递归算法
{
  for(l=1;l<n;l*=2) /*l为一趟归并段的段长
    for(i=0;(2*i-1)*l<n;i++) /*i为本趟的归并段序号
    {
      start1=2*l*i; /*求出待归并的两段的上下界
      end1=start1+l-1;
      start2=end1+1;
      end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);/*注重end2可能超出边界
      Merge(a,start1,end1,start2,end2); /*归并
    }
}/*Merge_Sort
void Merge(int a[ ],int s1,int e1,int s2,int e2)/*将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]
{
  int b[MAXSIZE]; /*设立辅助存储数组b
  for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)
  {
    if(a[i]<a[j]) b[k]=a[i++];
    else b[k]=a[j++];
  }
  while(i<=e1) b[k++]=a[i++];
  while(j<=e2) b[k++]=a[j++]; /*归并到b中
  for(i=s1;i<=e2;i++) /*复制回去
    a[i]=b[i];
}/*Merge
10.37
void LinkedList_Merge_Sort1(LinkedList &L)/*链表结构上的归并排序非递归算法
{
  for(l=1;l<L.length;l*=2) /*l为一趟归并段的段长
    for(p=L->next,e2=p;p->next;p=e2)
    {
      for(i=1,q=p;i<=l&&q->next;i++,q=q->next);
      e1=q;
      for(i=1;i<=l&&q->next;i++,q=q->next);
      e2=q; /*求出两个待归并子序列的尾指针
      if(e1!=e2) LinkedList_Merge(L,p,e1,e2); /*归并
    }
}/*LinkedList_Merge_Sort1
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)/*对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
  q=p->next;r=e1->next; /*q和r为两个子序列的起始位置
  while(q!=e1->next&&r!=e2->next)
  {
    if(q->data<r->data) /*选择要害字较小的那个结点接在p的后面
    {
      p->next=q;p=q;
      q=q->next;
    }
    else
    {
      p->next=r;p=r;
      r=r->next;
    }
  }/*while
  while(q!=e1->next) /*接上剩余部分
  {
    p->next=q;p=q;
    q=q->next;
  }
  while(r!=e2->next)
  {
    p->next=r;p=r;
    r=r->next;
  }
}/*LinkedList_Merge
10.38
void LinkedList_Merge_Sort2(LinkedList &L)/*初始归并段为最大有序子序列的归并排序,采用链表存储结构
{
  LNode *end[MAXSIZE]; /*设立一个数组来存储各有序子序列的尾指针
  for(p=L->next->next,i=0;p;p=p->next) /*求各有序子序列的尾指针
    if(!p->next||p->data>p->next->data) end[i++]=p;
  while(end[0]->next) /*当不止一个子序列时进行两两归并
  {
    j=0;k=0; /*j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置
    for(p=L->next,e2=p;p->next;p=e2) /*两两归并所有子序列
    {
      e1=end[j];e2=end[j+1]; /*确定两个子序列
      if(e1->next) LinkedList_Merge(L,p,e1,e2); /*归并
      end[k++]=e2; /*用新序列的尾指针取代原来的尾指针
      j+=2; /*转到后面两个子序列
    }
  }/*while
}/*LinkedList_Merge_Sort2
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)/*对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
  q=p->next;r=e1->next;
  while(q!=e1->next&&r!=e2->next)
  {
    if(q->data<r->data)
    {
      p->next=q;p=q;
      q=q->next;
    }
    else
    {
      p->next=r;p=r;
      r=r->next;
    }
  }/*while
  while(q!=e1->next)
  {
    p->next=q;p=q;
    q=q->next;
  }
  while(r!=e2->next)
  {
    p->next=r;p=r;
    r=r->next;
  }
}/*LinkedList_Merge,与上一题完全相同
10.39
void SL_Merge(int a[ ],int l1,int l2)/*把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列
{
  start1=0;start2=l1; /*分别表示序列1和序列2的剩余未归并部分的起始位置
  for(i=0;i<l1;i++) /*插入第i个元素
  {
    for(j=start2;j<l1+l2&&a[j]<a[start1+i];j++); /*寻找插入位置
    k=j-start2; /*k为要向右循环移动的位数
    RSh(a,start1,j-1,k);/*将a[start1]到a[j-1]之间的子序列循环右移k位
    start1+=k+1;
    start2=j; /*修改两序列尚未归并部分的起始位置
  }
}/*SL_Merge
void RSh(int a[ ],int start,int end,int k)/*将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18
{
  len=end-start+1;
  for(i=1;i<=k;i++)
    if(len%i==0&&k%i==0) p=i; /*求len和k的最大公约数p
  for(i=0;i<p;i++) /*对p个循环链分别进行右移
  {
    j=start+i;l=start+(i+k)%len;temp=a[j];
    while(l!=start+i)
    {
      a[j]=temp;
      temp=a[l];
      a[l]=a[j];
      j=l;l=start+(j-start+k)%len; /*依次向右移
    }
    a[start+i]=temp;
  }/*for
}/*RSh
10.40
书后给出的解题思路在表述上存在问题,无法理解.比如说,"把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1<s,第二个子序列有s个记录."可是题目中并没有说明,第一个序列的长度<2s.请会做的朋友提供解法.
10.41
void Hash_Sort(int a[ ])/*对1000个要害字为四位整数的记录进行排序
{
  int b[10000];
  for(i=0;i<1000;i++) /*直接按关 键字散列
  {
    for(j=a[i];b[j];j=(j+1)%10000);
    b[j]=a[i];
  }
  for(i=0,j=0;i<1000;j++) /*将散列收回a中
    if(b[j])
    {
      for(x=b[j],k=j;b[k];k=(k+1)%10000)
        if(b[k]==x)
        {
          a[i++]=x;
          b[k]=0;
        }
    }/*if
}/*Hash_Sort
10.42
typedef struct {
                     int gt; /*大于该记录的个数
                     int lt; /*小于该记录的个数
                   } place; /*整个序列中比某个要害字大或小的记录个数
int Get_Mid(int a[ ],int n)/*求一个序列的中值记录的位置
{
  place b[MAXSIZE];
  for(i=0;i<n;i++) /*对每一个元素统计比它大和比它小的元素个数gt和lt
    for(j=0;j<n;j++)
    {
      if(a[j]>a[i]) b[i].gt++;
      else if(a[j]<a[i]) b[i].lt++;
    }
  mid=0;
  min_dif=abs(b[0].gt-b[0].lt);
  for(i=0;i<n;i++) /*找出gt值与lt值最接近的元素,即为中值记录
    if(abs(b[i].gt-b[i].lt)<min_dif) mid=i;
  return mid;
}/*Get_Mid
10.43
void Count_Sort(int a[ ],int n)/*计数排序算法
{
  int c[MAXSIZE];
  for(i=0;i<n;i++) /*对每一个元素
  {
    for(j=0,count=0;j<n;j++) /*统计要害字比它小的元素个数
      if(a[j]<a[i]) count++:
    c[i]=count;
  }
  for(i=0;i<n;i++) /*依次求出要害字最小,第二小,...,最大的记录
  {
    min=0;
    for(j=0;j<n;j++)
      if(c[j]<c[min]) min=j; /*求出最小记录的下标min
    a[i]<->a[min]; /*与第i个记录交换
    c[min]=INFINITY; /*修改该记录的c值为无穷大以便下一次选取
  }
}/*Count_Sort
10.44
void Enum_Sort(int a[ ],int n)/*对要害字只能取v到w之间任意整数的序列进行排序
{
  int number[w+1],pos[w+1];
  for(i=0;i<n;i++) number[a[i>++; /*计数
  for(pos[0]=0,i=1;i<n;i++)
    pos[i]=pos[i-1]+num[i]; /*pos数组可以把要害字的值映射为元素在排好的序列中的位置
  for(i=0;i<n;i++) /*构造有序数组c
    c[pos[a[i>++]=a[i];
  for(i=0;i<n;i++)
    a[i]=c[i];
}/*Enum_Sort
分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用.
10.45
typedef enum {0,1,2,3,4,5,6,7,8,9} digit; /*个位数类型
typedef digit[3] num; /*3位自然数类型,假设低位存储在低下标,高位存储在高下标
void Enum_Radix_Sort(num a[ ],int n)/*利用计数实现基数排序,其中要害字为3位自然数,共有n个自然数
{
  int number ,pos ;
  num c[MAXSIZE];
  for(j=0;j<3;j++) /*依次对个位,十位和百位排序
  {
    for(i=0;i<n;i++) number[a[i][j>++; /*计数
    for(pos[0]=0,i=1;i<n;i++)
      pos[i]=pos[i-1]+num[i]; /*把要害字的值映射为元素在排好的序列中的位置
    for(i=0;i<n;i++) /*构造有序数组c
      c[pos[a[i][j>++]=a[i];
    for(i=0;i<n;i++)
      a[i]=c[i];
  }/*for
}/*Enum_Radix_Sort
分析:计数排序是一种稳定的排序方法.正因为如此,它才能够被用来实现基数排序.
10.46
typedef struct {
                     int key;
                     int pos;
                   } Shadow; /*影子序列的记录类型
void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)/*对元素很大的记录序列b进行排序,结果放入a中,不移动元素
{
  Shadow d[MAXSIZE];
  for(i=0;i<n;i++) /*生成影子序列
  {
    d[i].key=b[i].key;
    d[i].pos=i;
  }
  for(i=n-1,change=1;i>1&&change;i--) /*对影子序列执行冒泡排序
  {
    change=0;
    for(j=0;j<i;j++)
      if(d[j].key>d[j+1].key)
      {
        d[j]<->d[j+1];
        change=1;
      }
  }/*for
  for(i=0;i<n;i++) /*按照影子序列里记录的原来位置复制原序列
    a[i]=b[d[i].pos];
}/*Shadow_Sort

<  全文完  >