南邮mooc-数据结构第十章—排序作业参考答案数据结构与算法qq43656353的博客-

1 ( 65分 )
设待排序数据元素的关键字为：65,78,21,30,80,7,79,57,35,26，请按照下列算法对这组数据元素按关键字升序排序（以教材所给出算法为标准），给出每个算法的前2趟排序结果。
注意：不要写错关键字造成扣分，比如35写成36

A.直接插入排序；
B.简单选择排序；
C.冒泡排序；
D.快速排序；
E.两路合并排序；
F.堆排序（注意要先给出调整好的最大堆，再写前2趟结果）.

F.堆排序（注意要先给出调整好的最大堆，再写前2趟结果）. 过程

2 ( 20分 )
请对元素序列27, 6, 32, 48, 26, 17, 63进行排序（注意：不要写错关键字造成扣分）：
(1) 请用直接插入排序算法进行排序，写出第一趟排序结果：____________。
(2) 请用冒泡排序算法进行排序，写出第一趟排序结果：____________。
(3) 请用两路合并排序算法进行排序，写出第一趟排序结果：____________。
(4) 请用快速排序算法进行排序，写出第一趟排序结果：____________。

3 ( 15分 )
已知一组待排序元素关键字为：24,33,12,17,33,15,12
请写出3趟快速排序的结果（注意以下划线区分相同关键字，结果没标明下划线判错）。

4 ( 20分 )
待排序数据元素以单链表方式存储，完成下列基于单链表的简单选择排序算法。
单链表结点结构体定义如下：

typedef struct node{ int key; //简单起见，只定义排序关键字且为整数 struct node* link; //指针域 }Node; void SelectSort(Node *first) {    Node * small, p, q; int temp; for (p=first; (1) ; (2) ){        small=p; for (q=p->link; q!=NULL; q=q->link) // 找最小值 if ( (3) ) //                       small=q; //元素值交换     temp = p->data; (4) ; (5) ; } } 

参考答案示例

#include <stdio.h> #include <stdlib.h> typedef struct node{ int data; //简单起见，只定义排序关键字且为整数 struct node* link; //指针域 }Node; void SelectSort(Node *first) {    Node *small, *p, *q; int temp; for (p=first; p!=NULL; p=p->link) {         small=p; for (q=p->link; q!=NULL; q=q->link) // 找最小值 { if (small->data > q->data) //                         small=q; } //元素值交换     temp = p->data;    p->data = small->data;    small->data = temp; } } int main() {         Node * first = (Node *)malloc(sizeof(Node *));         first->data = 10;         first->link = NULL;         Node * second = (Node *)malloc(sizeof(Node *));         second->data = 8;         second->link = NULL;         first->link = second;         Node * third = (Node *)malloc(sizeof(Node *));         third->data = 4;         third->link = NULL;         second->link = third;         Node * fourth = (Node *)malloc(sizeof(Node *));         fourth->data = 2;         fourth->link = NULL;         third->link = fourth;         Node * firth = (Node *)malloc(sizeof(Node *));         firth->data = 3;         firth->link = NULL;         fourth->link = firth; SelectSort(first); for(Node *p = first; p != NULL; p=p->link) { printf("%d  ",p->data); } for(Node *q = first; q != NULL; q=q->link) { free(q); } return 0; }  运行示例： ------------------- 2 3 4 8 10 % ------------------- 

关于南邮mooc 的作业已经收尾，后续会陆续上传关于数据结构的整理的复习资料！，请需要的小伙伴关注一下动态！你的随手鼓励，是我不断创作的最大动力！感谢🙏