数据结构(C语言第2版) 课后习题答案之 第八章 排序

目录

第8章  排序

1．选择题

2．应用题

（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。

3．算法设计题

（1）试以单链表为存储结构，实现简单选择排序算法。

（2）有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。

（3）设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。

（4）编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

（5）借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。

（6）有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。

第8章  排序 1．选择题

（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（   ）。

A．归并排序       B．冒泡排序        C．插入排序        D．选择排序

（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（   ）。

A．归并排序       B．冒泡排序        C．插入排序        D．选择排序

（3）对n个不同的关键字由小到大进行冒泡排序，在下列（   ）情况下比较的次数最多。

A．从小到大排列好的                 B．从大到小排列好的    

 C．元素无序                         D．元素基本有序

（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（   ）。

A．n+1            B．n               C．n-1              D．n(n-1)/2

（5）快速排序在下列（   ）情况下最易发挥其长处。

A．被排序的数据中含有多个相同排序码   

B．被排序的数据已基本有序   

C．被排序的数据完全无序         

D．被排序的数据中的最大值和最小值相差悬殊

（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（   ）。

A．O(n)           B．O(n2)            C．O(nlog2n)         D．O(n3) 

（7）若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（   ）。

A．38，40，46，56，79，84               B．40，38，46，79，56，84

C．40，38，46，56，79，84               D．40，38，46，84，56，79

（8）下列关键字序列中，（   ）是堆。

A．16，72，31，23，94，53               B．94，23，31，72，16，53

C．16，53，23，94，31，72               D．16，23，53，31，94，72

（9）堆是一种（   ）排序。

A．插入         B．选择         C．交换      D．归并

（10）堆的形状是一棵（   ）。

A．二叉排序树          B．满二叉树         C．完全二叉树     D．平衡二叉树

（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（   ）。

A．79，46，56，38，40，84               B．84，79，56，38，40，46          

C．84，79，56，46，40，38               D．84，56，79，40，46，38

（12）下述几种排序方法中，要求内存最大的是（   ）。

A．希尔排序        B．快速排序         C．归并排序       D．堆排序

（13）下述几种排序方法中，（   ）是稳定的排序方法。

A．希尔排序        B．快速排序         C．归并排序       D．堆排序

（14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用(    )算法最节省时间。

A．冒泡排序        B．快速排序         C．简单选择排序   D．堆排序

（15）下列排序算法中，（   ）不能保证每趟排序至少能将一个元素放到其最终的位置上。

A．希尔排序        B．快速排序         C．冒泡排序       D．堆排序

2．应用题 （1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。

① 直接插入排序

② 折半插入排序

③ 希尔排序（增量选取5，3，1）

④ 冒泡排序

⑤ 快速排序

⑥ 简单选择排序

⑦ 堆排序

⑧ 二路归并排序

①直接插入排序

[2    12]   16   30   28   10   16*   20   6    18         

[2    12    16]  30   28   10   16*   20   6    18         

[2    12    16   30]  28   10   16*   20   6    18         

[2    12    16   28   30]  10   16*   20   6    18         

[2    10    12   16   28  30]   16*   20   6    18         

[2    10    12   16   16*  28   30]   20   6    18         

[2    10    12   16   16*  20   28   30]   6    18         

[2    6     10   12   16  16*   20   28   30]   18         

[2    6     10   12   16  16*    18   20   28   30]

② 折半插入排序 排序过程同①

③ 希尔排序（增量选取5，3，1）

10   2    16   6    18   12   16*   20  30    28 （增量选取5）

6    2    12   10   18   16   16*   20  30    28 （增量选取3）

2    6    10   12   16   16*  18      20  28    30 （增量选取1）

④ 冒泡排序

2    12   16    28   10   16*  20   6     18   [30]        

2    12   16    10   16*  20   6    18    [28   30]        

2    12   10    16   16*  6     18   [20   28   30]          

2    10   12    16   6   16*    [18   20   28   30]          

2    10   12    6   16   [16*    18   20   28   30]         

2    10   6    12   [16   16*    18   20   28   30]        

2    6   10    [12   16   16*    18   20   28   30]

2    6   10    12   16   16*    18   20   28   30]       

⑤ 快速排序

12  [6    2  10]  12  [28  30  16*  20   16  18]          

6   [2]  6   [10]  12  [28  30  16*  20   16  18 ]         

28  2    6   10   12  [18  16  16*  20 ] 28  [30 ]       

18  2   6   10  12   [16*  16]  18  [20]  28  30          

16*     2   6   10  12   16* [16]   18  20   28  30

左子序列递归深度为1，右子序列递归深度为3

⑥ 简单选择排序

2    [12   16   30   28   10   16*   20   6    18]          

2    6    [16   30   28   10   16*   20   12   18]          

2    6    10   [30   28   16   16*   20   12   18]          

2    6    10   12   [28   16   16*   20   30   18]          

2    6    10   12   16   [28   16*   20   30   18]          

2    6    10   12   16   16*    [28  20   30   18]          

2    6    10   12   16   16*   18   [20   30   28]         

2    6    10   12   16   16*   18    20   [28  30]         

2    6    10   12   16   16*    18   20   28   [30]

⑧ 二路归并排序

2 12    16 30    10 28    16 * 20    6 18                                                

2 12 16 30        10 16* 20 28       6 18                                               

2 10 12 16 16* 20 28 30   6 18                                               

2 6 10 12 16 16* 18 20 28 30

⑦ 堆排序

第一步,形成初始大根堆（详细过程略），第二步做堆排序。

  

3．算法设计题 （1）试以单链表为存储结构，实现简单选择排序算法。

void LinkedListSelectSort(LinkedList head)

//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下

//当前结点和最小结点的前驱指针

p=head->next;

while(p!=null)

    {q=p->next;  r=p;    //设r是指向关键字最小的结点的指针

     while (q!=null)

      {if(q->datadata) r=q;

 q:=q->next;

}

     if(r!=p)  r->datap->data;

     p=p->next;

    }

（2）有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。

（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。   

typedef struct node

       { ElemType data;

         struct node *prior,*next;

       }node，*DLinkedList;

void  TwoWayBubbleSort(DLinkedList la)

//对存储在带头结点的双向链表la中的元素进行双向起泡排序。

{int exchange=1;  // 设标记

 DLinkedList p,temp,tail;

 head=la         //双向链表头，算法过程中是向下起泡的开始结点

 tail=null;      //双向链表尾，算法过程中是向上起泡的开始结点

while (exchange)

{p=head->next;    //p是工作指针，指向当前结点

exchange=0;      //假定本趟无交换

while (p->next!=tail)  // 向下（右）起泡，一趟有一最大元素沉底

  if (p->data>p->next->data) //交换两结点指针，涉及6条链

{temp=p->next; exchange=1;//有交换

p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下

temp->next=p; p->prior->next=temp;     //将temp插到p结点前

temp->prior=p->prior; p->prior=temp;

}

          else p=p->next; //无交换，指针后移

          tail=p; //准备向上起泡

          p=tail->prior;

while (exchange && p->prior!=head)  //向上（左）起泡，一趟有一最小元素冒出

     if (p->dataprior->data)       //交换两结点指针，涉及6条链

{temp=p->prior; exchange=1;     //有交换

p->prior=temp->prior;temp->prior->next=p； //先将temp结点从链表上摘下

temp->prior=p; p->next->prior=temp;        //将temp插到p结点后（右）

temp->next=p->next; p->next=temp;

}

            else p=p->prior;  //无交换，指针前移

          head=p;             //准备向下起泡

 }// while (exchange)

} //算法结束

（3）设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。

要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。

[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白色砾石）和i=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;}

//左侧只有红色砾石，交换r[k]和r[i]

      else     {temp=r[j];r[j]=r[i];r[i]=temp; j++;  

  //左侧已有红色和白色砾石，先交换白色砾石到位

temp=r[k];r[k]=r[i];r[i]=temp; i++;

//白色砾石（i所指）和待定砾石（j所指）

}   //再交换r[k]和r[i]，使红色砾石入位。

if (r[k].key==2)

      if (ik为止。

算法片段如下：

int i=1,j=1,k=n;

while(j