数据结构实验四 排序算法的实现
广州大学学生实验报告
开课实验室：计算机科学与工程实验（电子楼416） 2019年6月4日
|
学院 |
计算机科学与教育软件学院 |
年级、专业、班 |
|
姓名 |
|
学号 |
|
|
|
实验课程名称 |
数据结构实验 |
成绩 |
|
|||||
|
实验项目名称 |
实验四 排序算法 |
指导老师 |
|
|||||
|
一、实验目的 掌握线性的定义及基本操作，用链表实现：遍历、查找、插入、删除、翻转。 二、使用仪器、器材 微机一台 操作系统：WinXP 编程软件：C++ 三、实验内容及原理 用随机函数生成16个2位正整数（10~99），从复杂度为O(n2) 的插入排序、选择排序、冒泡（双向冒泡）和复杂度为O(nlog2n) 的堆排序、快速排序、归并排序等多种排序算法各选1种实现，输出排序中间过程、统计关键字的比较次数和记录的移动次数。
直接插入排序 Main.cpp #include "stdafx.h" #include"InsertSort.h"
int main() { int n = 10; RecType R[MAXL]; KeyType a[] = { 9,8,7,6,5,4,3,2,1,0 }; CreateList(R, a, n); printf("排序前:"); DispList(R, n); int compare, move; InsertSort(R, n,compare,move); printf("排序后:"); DispList(R, n); printf("\n"); printf("关键字比较次数:%d \n",compare); printf("记录的移动次数:%d ",move); return 1; } InsertSort.h
//顺序表基本运算算法 #include <stdio.h> #define MAXL 100 //最大长度 typedef int KeyType; //定义关键字类型为int typedef char InfoType;
typedef struct { KeyType key; //关键字项 InfoType data; //其他数据项，类型为InfoType } RecType; //查找元素的类型
void swap(RecType x, RecType y); //x和y交换 void CreateList(RecType R[], KeyType keys[], int n);//创建顺序表 void DispList(RecType R[], int n); //输出顺序表 //-------------------------------------------------------------------直接插入排序算法 void InsertSort(RecType R[], int n, int& compare, int& move); //对R[0..n-1]按递增有序进行直接插入排序 InsertSort.cpp
#include"stdafx.h" #include"InsertSort.h" void swap(RecType x, RecType y) //x和y交换 { RecType tmp = x; x = y; y = tmp; }
void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表 { for (int i = 0; i<n; i++) //R[0..n-1]存放排序记录 R[i].key = keys[i]; } void DispList(RecType R[], int n) //输出顺序表 { for (int i = 0; i<n; i++) printf("%d ", R[i].key); printf("\n"); } //-------------------------------------------------------------------直接插入排序算法 void InsertSort(RecType R[], int n, int& compare, int& move) //对R[0..n-1]按递增有序进行直接插入排序 { int i, j; RecType tmp; compare=0; move = 0; for (i = 1; i<n; i++) { if (R[i].key<R[i - 1].key) //反序时 { compare++; tmp = R[i]; j = i - 1; do //找R[i]的插入位置 { R[j + 1] = R[j]; //将关键字大于R[i].key的记录后移 j--; move++; } while (j >= 0 && R[j].key>tmp.key); R[j + 1] = tmp; //在j+1处插入R[i] } printf(" i=%d: ", i); DispList(R, n); } } 堆排序 Main.cpp
//堆排序算法 #include"stdafx.h" #include "InsertSort.h"
int main() { int n = 10; int compare = 0; int move = 0; RecType R[MAXL]; KeyType a[] = { 15,18,29,12,35,32,27,23,10,20 }; CreateList1(R, a, n); printf("排序前:"); DispList1(R, n); HeapSort(R, n,compare,move); printf("排序后:"); DispList1(R, n); printf("关键字比较次数:%d \n",compare); printf("记录移动次数:%d \n",move); return 1; }
HeapSort.h
//顺序表基本运算算法 #include <stdio.h> #define MAXL 100 //最大长度 typedef int KeyType; //定义关键字类型为int typedef char InfoType;
typedef struct { KeyType key; //关键字项 InfoType data; //其他数据项，类型为InfoType } RecType; //查找元素的类型
//----以下运算针对堆排序的程序 void CreateList1(RecType R[], KeyType keys[], int n); //创建顺序表 void DispList1(RecType R[], int n); //输出顺序表 //-------------------------------------------------------------------直接插入排序算法 void sift(RecType R[], int low, int high, int&compare, int& move); void HeapSort(RecType R[], int n, int &compare, int &move);
HeapSort.h
#include"stdafx.h" #include"HeapSort.h" void CreateList1(RecType R[], KeyType keys[], int n) //创建顺序表 { for (int i = 1; i <= n; i++) //R[1..n]存放排序记录 R[i].key = keys[i - 1]; } void DispList1(RecType R[], int n) //输出顺序表 { for (int i = 1; i <= n; i++) printf("%d ", R[i].key); printf("\n"); } //-------------------------------------------------------------------直接插入排序算法 void sift(RecType R[], int low, int high,int&compare,int& move) { int i = low, j = 2 * i; //R[j]是R[i]的左孩子 RecType temp = R[i]; while (j <= high) { if (j < high && R[j].key < R[j + 1].key) //若右孩子较大,把j指向右孩子 { j++; compare++; } //变为2i+1 if (temp.key<R[j].key) { R[i] = R[j]; //将R[j]调整到双亲结点位置上 i = j; //修改i和j值,以便继续向下筛选 j = 2 * i; compare++; move++; } else break; //筛选结束 } R[i] = temp;//被筛选结点的值放入最终位置 }
void HeapSort(RecType R[], int n,int &compare,int &move) { compare = 0; move = 0; int i; RecType tmp; for (i = n / 2; i >= 1; i--) //循环建立初始堆,调用sift算法 n/2 次 sift(R, i, n, compare,move); printf("初始堆:"); DispList1(R, n); for (i = n; i >= 2; i--) //进行n-1趟完成推排序,每一趟堆排序的元素个数减1 { tmp = R[1]; //将最后一个元素与根R[1]交换 R[1] = R[i]; R[i] = tmp; move+=3; printf("第%d趟: ", n - i + 1); DispList1(R, n); sift(R, 1, i - 1, compare,move); //对R[1..i-1]进行筛选,得到i-1个节点的堆 printf("筛选为:"); DispList1(R, n); } }
五、实验结果及分析 1.直接插入排序
2.堆排序
|
||||||||
|
|
||||||||