河南理工大学
16 学年—17学年第 1 学期 数据结构 实验任务书
专业名称： 实验学时： 2
课程名称：数据结构 任课教师： 翟海霞
实验题目： 排序算法实现与比较
实验环境： Visual C++ 6.0
实验八：
实验目的和要求：熟悉多种排序算法，理解每种排序算法思想，掌握排序算法的基本设计方法，掌握排序算法时间复杂度和空间复杂度的分析方法。
实验内容：1.对所讲过算法深入理解。
2. 将冒泡排序再做进一步的优化。如果有100个数的数组，当前仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在该一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，下次只要从数组头部遍历到这个位置就可以了。
3. 试以单链表为存储结构，实现简单选择排序算法。
#include<stdio.h> #include<stdlib.h> #define Maxsize 20 typedef struct { int key; }RedType; typedef struct { RedType r[Maxsize+1]; int length; }SqList; void Bubblesort(SqList *L) { int i,j,n,change; RedType x; n=L->length;change=1; for(i=0;i<n-1&&change;++i) { change=0; for(j=0;j<n-i-1;++j) if(L->r[j].key>L->r[j+1].key) {x=L->r[j];L->r[j]=L->r[j+1];L->r[j+1]=x;change=1; } } } typedef struct Node { int date; struct Node *next; }node,*List; //创建单链表 List creat_list(int n) { int i=0; List head,L,temp; head=(List)malloc(sizeof(node)); head->next=NULL; temp=head; for(;i<n;i++) { L=(List)malloc(sizeof(node)); L->next=NULL; printf("Please input the date:"); scanf("%d",&L->date); temp->next=L; temp=L; } return head; } List getmin(List L) {//取得从指针L开始的链表中记录的最小值 List min; min=L; while(L->next) { if(min->date>(L->next->date)) { min=L->next; } L=L->next; } return min;//返回较小值的指针 } void selectsort(List head)//简单选择排序--单链表 { List j,i=head->next; int temp; for(;i->next!=NULL;i=i->next) { j=getmin(i); if(i->date!=j->date) { temp=i->date; i->date=j->date; j->date=temp; } } } //输出单链表 void printf_list(List head) { List p=head->next; while(p) { printf("=",p->date); p=p->next; } } int main() { List head,temp; SqList L,*p=&L; int i;L.length=10; int choose,n; printf("————————————排序算法与比较——————————\n\n"); printf("操作：\n"); printf("1.冒泡排序\n"); printf("2.简单选择排序\n"); printf("0.退出\n"); choose=-1; while(1) { printf("请输入您的操作:"); scanf("%d",&choose); switch(choose) { case 1:{ //printf("请输入数据个数:"); //scanf("%d",&n); printf("请输入数据:\n"); for(i=0;i<L.length;i++) scanf("%d",&L.r[i].key); printf("原数据："); for(i=0;i<L.length;i++) printf("M",L.r[i].key); Bubblesort(p); printf("\n排序后："); for(i=0;i<L.length;i++) printf("M",L.r[i].key); printf("\n"); } break; case 2:{ printf("请输入元素个数:"); scanf("%d",&n); head=creat_list(n); printf_list(head); printf("\n"); selectsort(head); printf_list(head); printf("\n"); }break; case 0:exit(0); } } return 0; }
