设为首页收藏本站
开启辅助访问

数据结构实验报告六 排序

 您所在的位置：网站首页 › 二叉树排序算法实验报告 › 数据结构实验报告六 排序

数据结构实验报告六 排序

2024-07-16 00:12:13| 来源: 网络整理| 查看: 265

一、实验目的

1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。

二、实验内容和要求 1.运行下面程序： #include #include #define MAX 50 int slist[MAX]; /*待排序序列*/ void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n); void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n); /*直接插入排序*/ void insertSort(int list[], int n) { int i = 1, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为："); printList(list, n); for(i = 2; i list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v) { int i = u, j , temp = list[i]; j = 2 * i; while (j list[i] = list[j]; /*将list[j]调到父亲的位置上*/ i = j; j = 2 * i; /*修改i和j的值，以便继续向下筛选*/ } else break; /*筛选完成，终止循环*/ } list[i] = temp; /*被筛结点的值放入最终位置*/ } void heapSort(int list[], int n) { int i = 0, temp = 0, count = 1; printf("对序列进行堆排序：\n"); printf("初始序列为："); printList(list, n); for (i = n / 2; i > 0; i--) heapAdjust(list, i, n); /*建立初始堆*/ printf("建立的初始堆为："); printList(list, n); for(i = n ; i > 1; i--) {/*循环，完成堆排序*/ temp = list[1]; list[1] = list[i]; list[i] = temp; /*将第一个元素同当前区间内最后一个元素对换*/ heapAdjust(list, 1 , i-1); /*筛选出list[1]结点*/ printf("第%d次排序结果：", count++); printList(list, n); } } /*生成待排序序列*/ void createList(int list[], int *n) { int i = 1,a; printf("请输入待排序序列(长度小于50,以输入一个字符结束):\n"); while(scanf("%d",&a)==1) { list[i] = a; i++; } *n=i-1; getchar(); } /*输出排序结果*/ void printList(int list[], int n) { int i = 1; for(; i int choice=1,length; while(choice!=0) { printf("\n"); printf("***** 内部排序算法演示程序 *****\n"); printf("\n1. 直接插入排序 \n"); printf("\n2. 堆排序 \n"); printf("\n0. 退出\n"); printf("\n请选择："); scanf("%d", &choice); getchar(); switch(choice) { case 1: { createList(slist, &length); insertSort(slist, length); break; } case 2: { createList(slist, &length); heapSort(slist, length); break; } default:choice=0; } printf("\n"); } return 0; }

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

1） 直接插入排序运行结果（写出每一趟的状态）：

对序列进行直接插入排序： 初始序列为： 49 38 65 97 13 27 49 第1次排序结果： 38 49 65 97 13 27 49 第2次排序结果： 38 49 65 97 13 27 49 第3次排序结果： 38 49 65 97 13 27 49 第4次排序结果： 13 38 49 65 97 27 49 第5次排序结果： 13 27 38 49 65 97 49 第6次排序结果： 13 27 38 49 49 65 97 实验六（1）

2）堆排序运行结果（写出每一趟的状态）：

对序列进行堆排序： 初始序列为： 49 38 65 97 13 27 49 建立的初始堆为： 97 49 65 38 13 27 49 第1次排序结果： 65 49 49 38 13 27 97 第2次排序结果： 49 38 49 27 13 65 97 第3次排序结果： 49 38 13 27 49 65 97 第4次排序结果： 38 27 13 49 49 65 97 第5次排序结果： 27 13 38 49 49 65 97 第6次排序结果： 13 27 38 49 49 65 97 实验六（2）

2、在1题中补充希尔排序算法。 算法代码： void shellSort(int list[], int n) { int i,j,d,temp,count=1; printf("对序列进行希尔排序：\n"); printf("初始序列为："); printList(list, n); for(d=n/2;d>0;d/=2) { for(i=d+1;i list[j+d]=list[j]; j=j-d; } list[j+d]=temp; } printf("第%d次排序结果：", count++); printList(list, n); } }

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）

运行结果（写出每一趟的状态）：

对序列进行希尔排序： 初始序列为： 49 38 65 97 13 27 49 第1次排序结果： 49 13 27 49 38 65 97 第2次排序结果： 13 27 38 49 49 65 97 实验六（3）

3、在1题中补充快速排序算法。 算法代码： int count=1; int Partition(int list[], int i, int j, int n) { list[0]=list[i]; int pivotkey=list[i]; while(i int pivot; if(i int i = 1, j = 0, node = 0, count = 1; printf("对序列进行直接插入排序：\n"); printf("初始序列为："); printList(list, n); for(i = 2; i list[j+1] = list[j]; --j; } list[j+1] = node; printf("第%d次排序结果：", count++); printList(list, n); } } /*堆排序*/ void heapAdjust(int list[], int u, int v) { int i = u, j, temp = list[i]; j = 2 * i; while (j list[i] = list[j]; /*将list[j]调到父亲的位置上*/ i = j; j = 2 * i; /*修改i和j的值，以便继续向下筛选*/ } else break; /*筛选完成，终止循环*/ } list[i] = temp; /*被筛结点的值放入最终位置*/ } void heapSort(int list[], int n) { int i = 0, temp = 0, count = 1; printf("对序列进行堆排序：\n"); printf("初始序列为："); printList(list, n); for (i = n / 2; i > 0; i--) heapAdjust(list, i, n); /*建立初始堆*/ printf("建立的初始堆为："); printList(list, n); for(i = n ; i > 1; i--) { /*循环，完成堆排序*/ temp = list[1]; list[1] = list[i]; list[i] = temp; /*将第一个元素同当前区间内最后一个元素对换*/ heapAdjust(list, 1, i-1); /*筛选出list[1]结点*/ printf("第%d次排序结果：", count++); printList(list, n); } } /*希尔排序*/ void shellSort(int list[], int n) { int i,j,d,temp,count=1; printf("对序列进行希尔排序：\n"); printf("初始序列为："); printList(list, n); for(d=n/2; d>0; d/=2) { for(i=d+1; i list[j+d]=list[j]; j=j-d; } list[j+d]=temp; } printf("第%d次排序结果：", count++); printList(list, n); } } /*快速排序*/ int count=1; int Partition(int list[], int i, int j, int n) { list[0]=list[i]; int pivotkey=list[i]; while(i int pivot; if(i int i = 1,a; printf("请输入待排序序列(长度小于50,以输入一个字符结束):\n"); while(scanf("%d",&a)==1) { list[i] = a; i++; } *n=i-1; getchar(); } /*输出排序结果*/ void printList(int list[], int n) { int i = 1; for(; i int choice=1,length; while(choice!=0) { printf("\n"); printf("***** 内部排序算法演示程序 *****\n"); printf("\n1. 直接插入排序 \n"); printf("\n2. 堆排序 \n"); printf("\n3. 希尔排序 \n"); printf("\n4. 快速排序 \n"); printf("\n0. 退出\n"); printf("\n请选择："); scanf("%d", &choice); getchar(); switch(choice) { case 1: { createList(slist, &length); insertSort(slist, length); break; } case 2: { createList(slist, &length); heapSort(slist, length); break; } case 3: { createList(slist, &length); shellSort(slist, length); break; } case 4: { createList(slist, &length); printf("对序列进行快速排序：\n"); printf("初始序列为："); printList(slist, length); quickSort(slist, 1, length, length); break; } default: choice=0; } printf("\n"); } return 0; }


【本文地址】

公司简介

联系我们

今日新闻

点击排行
实验室常用的仪器、试剂和
说到实验室常用到的东西，主要就分为仪器、试剂和耗
不用再找了，全球10大实验
01、赛默飞世尔科技（热电）Thermo Fisher Scientif
三代水柜的量产巅峰T-72坦
作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这
通风柜跟实验室通风系统有
说到通风柜跟实验室通风，不少人都纠结二者到底是不
集消毒杀菌、烘干收纳为一
厨房是家里细菌较多的地方，潮湿的环境、没有完全密
实验室设备之全钢实验台如
全钢实验台是实验室家具中较为重要的家具之一，很多

推荐新闻

图片新闻
实验室药品柜的特性有哪些
实验室药品柜是实验室家具的重要组成部分之一，主要
小学科学实验中有哪些教学
计算机 计算器 一般 打孔器 打气筒 仪器车 显微镜
实验室各种仪器原理动图讲
1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分
高中化学常见仪器及实验装
1、可加热仪器：2、计量仪器：（1）仪器A的名称：量
微生物操作主要设备和器具
今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦
浅谈通风柜使用基本常识
　众所周知，通风柜功能中最主要的就是排气功能。在

专题文章
    CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭