内排序实习总结

发布时间:2017-01-12 来源: 实习总结 点击:

篇一:数据结构实习报告_排序

数据结构课程设计

实习报告

题 目:

学 号:

姓 名:

年 级:

学 院:

专 业:

完成日期:

授课教师:四个排序算法的比较 1210522 何厚华 大二 计算机与控制工程学院 计算机科学与技术 2014年5月25日 辛运帏

目录

1.题目................................................ 2

2.要求 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 2

3.程序实现 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 2

3.1程序运行及编译环境... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 2

3.2程序描述 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 2

3.3实现功能 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 3

3.3.1子功能模块 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... 3

3.3.1.1 子功能模块1 ... ... ... ... ... ... ... ... ... ... ... ... ...... ... 3

3.3.1.2子功能模块2... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4

3.3.1.3子功能模块3... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4

3.3.1.4子功能模块4... ... ... ... ... ... ... ... ... ... ... ... ... ... 6

3.3.1.5子功能模块5.. ... ... ... ... ... ... ... ... ... ... ... ... ... ... 7

3.3.1.6子功能模块6.. ... ... ... ... ... ... ... ... ... ... ... ... ... ...8

3.3.1.7子功能模块7.. ... ... ... ... ... ... ... ... ... ... ... ... ... ...9 3.3.2 数据结构... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10

3.3.3算法及程序说明... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10

3.4运行结果.. ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .... .... ... 12

3.5尚未解决的问题 .... ... ... ... ... ... ... ... ... ... ... ... ... ... .... .... .... ... 15

1.题目

四个排序算法的比较

给定N个int类型(自定义N的上限M,例如M=100000,N的取值不能少于10000)的整数,分别使用插入排序、快速排序、希尔排序和堆排序方法进行升序排序。

具体要求:

1 四种排序方法均能得到正确的排序结果。

2 分别统计四种排序中关键字比较的次数和记录交换的次数,并将统计结果显示出来。

2.要求:

初始数据使用随机数发生器产生,并使用程序自动检验排序结果的正确性。同时,需要编写一个检验随机性的小测试程序,分别统计各数段间数据的个数。数段的划分自定。例如可以按1000为一单位,分别统计(0,999)、(1000,1999)、…(N-1000,N-1)之间的数据个数。如果N较大,也可以按10000为一单位。总之,只要能说明问题即可。在一个数段内,还可以再分析各子数段中数据的个数,例如选定(1000,1999)数段,然后以100为一单位,统计这10个子数段中的数据个数。

3.程序实现

3.1程序运行及编译环境

程序是用Visual Studio 2010即VS10.0 编译的。可以在windows系列的操作系统上运行。

3.2程序描述

该程序主要用于实现了插入排序,希尔排序,快速排序和堆排序的算法,然后比较各种算法在系统产生的上万个随机数下排序的各种参数,这些参数主要有:比较次数,移动次数,交换次数,排序耗时。然后,验证了每一种排序结果的正确性,最后,统计了随机数组的分布情况,以判断系统产生的随机数是否均匀。其流程如下:

A).产生上万个随机数,并处理成满足范围条件的随机数

B).依次进行插入排序,希尔排序,快速排序,堆排序并且获得它们的主要参数

C).验证排序结果的正确性

D).统计随机数的区间分布

E).完成

3.3实现功能

A.统计随机数的区间分布

B.检验排序结果的正确性

C.实现插入排序算法

D.实现希尔排序算法

E.实现快速排序算法

F.实现建堆,整堆算法

G.在建堆,整堆的基础上实现堆排序的算法

3.3.1 子功能模块

3.3.1.1 子功能模块1

/***************************************************************

函数原型:void RandomTest(int a[],int n);

函数参数:a[]表示测试的数组,n表示数组元素个数

函数功能:随机性检测,把它们分到50个区间里面去

****************************************************************/

void RandomTest(int a[],int n){

cout<<"["<<setw(5)<<i*interval<<","<<setw(6)<<(i+1)*interval<<")"<<setw(6)<<Count[i]<<endl; }

int interval=MAXIMUM/INTERVALCOUNT; int Count[INTERVALCOUNT]; for(int i=0;i<INTERVALCOUNT;i++) Count[i]=0; for(int i=0;i<n;i++) Count[a[i]/interval]++;//把这个数加入到对应的区间中去 cout<<"统计结果如下:"<<endl<<"区间 个数"<<endl; for(int i=0;i<INTERVALCOUNT;i++){

}

3.3.1.2子功能模块2

/***************************************************************************** 函数原型:bool IsOrder(int a[],int n,bool IsReverse=false);

函数参数:int a[]表示待判断的数组

int n表示数组的前n项

bool IsReverse=false,表示这个数组按照升序还是反序排列,默认为升序 函数功能:用于判断排序结果的正确性

***************************************************************************/ bool IsOrder(int a[],int n,bool IsReverse=false){//true,表降序,false,表升序

}

switch (IsReverse){ case true:for(int i=1;i<n-1;i++)if(a[i]<a[i+1]){ } cout<<"排序有误!请检查排序算法!"<<endl;//检测到有逆序排列的 //cout<<i<<" "<<a[i]<<" "<<i+1<<""<<a[i+1]<<endl; return false; cout<<"恭喜你,排序算法成功!"<<endl; return true; case false: } return true; …………

3.3.1.3子功能模块3

/***************************************************************************** 函数原型:void InsertSort(int a[],int &Compare,int& Swap,int& Move,float& time,int n=MAXCOUNT);

篇二:实习5:排序

实习4:排序

1、实验目的

通过编写和调用学过的五个排序算法实现数据排序,充分理解各种排序算法的算法思想及各自的时间复杂度、稳定性。

2、实验内容

(一)参照课本,编写一个Java程序,实现顺序表记录类RecordNode。

(二)参照课本,编写一个Java程序,实现顺序表记录关键字类KeyType。

(三)参照课本,编写一个Java程序,实现顺序表类SeqList,并在其中添加成员函数:

(1)length()求顺序表的当前长度;

(2)display()输出数组元素的关键字;

(3)不带监视哨的直接插入排序算法;

(4)带监视哨的直接插入排序算法;

(5)希尔排序算法;

(6)起泡排序算法;

(7)快速排序算法。

(四)编写主程序,循环选择调用以上5个排序算法,对数组元素排序,并输出排序前后的数组元素。

(五)编译、运行、调试,观察排序效果。

篇三:实习六:内部排序

实验报告

题目:内部排序算法比较

一.需求分析

(1) 对以下6种常见的内部排序算法进行比较:起泡排序,直接插

入排序,简单选择排序,快速排序,希尔排序,堆排序。

(2) 待排序表的表长不小于100;其中的数据要用伪随机数产生;

至少要用5组不同的输入数据作比较;比较的指标为关键字参加的比较次数和关键字的移动次数。

(3) 最后要对结果作出简单分析,包括对各组数据的出结果波动大

小的解释。

测试数据有随机数产生器产生。

二.详细设计

#include <ctime>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LT(a, b) (++cmp_num, ((a) < (b)))

#define MAX_SIZE 10000

#define MAXV 1000000

using namespace std;

typedef int KeyType;

typedef struct _RedType

{

KeyType key;

} RedType;

typedef struct _SqList

{

RedType r[MAX_SIZE + 1]; int length;

} SqList;

typedef SqList HeapType;

typedef void SortProc(SqList &L, int &cmp_num, int &move_num);

void InsertSort(SqList &L, int &cmp_num, int &move_num) {

// 对顺序表L作直接插入排序 cmp_num = move_num = 0; for (int i = 2; i <= L.length; ++i) if (LT(L.r[i].key, L.r[i - 1].key)) { int j;

}

L.r[i] = L.r[i - 1]; } for (j = i - 2; LT(L.r[0].key, L.r[j].key); --j) L.r[j + 1] = L.r[j], move_num++; L.r[j + 1] = L.r[0]; move_num += 3; // 关键字交换记为3次移动

void BubbleSort(SqList &L, int &cmp_num, int &move_num) {

// 对顺序表L作起泡排序 cmp_num = move_num = 0; for (int i = 1; i < L.length; ++i) for (int j = L.length - 1; j >= i; j--) if (LT(L.r[j + 1].key, L.r[j].key)) { L.r[0] = L.r[j + 1]; L.r[j + 1] = L.r[j]; L.r[j] = L.(转载于:www.XltkWJ.Com 小 龙文档 网:内排序实习总结)r[0]; move_num += 3;

}

}

void SelectSort(SqList &L, int &cmp_num, int &move_num) {

// 对顺序表L作简单选择排序

cmp_num = move_num = 0;

for (int i = 1; i < L.length; ++i)

{

int m = i;

for (int j = i + 1; j <= L.length; j++)

if (LT(L.r[j].key, L.r[m].key))

m = j;

swap(L.r[i], L.r[m]);

move_num += 3;

}

}

void QSort(SqList &L, int low, int high, int &cmp_num, &move_num)

{

// 对顺序表L中的子序列L.r[low..high]作快速排序 int

} if (low < high) {} int l = low, r = high; KeyType base = L.r[low].key; L.r[0] = L.r[low]; while (l < r) { } L.r[l] = L.r[0]; move_num += 2; QSort(L, low, l - 1, cmp_num, move_num); QSort(L, l + 1, high, cmp_num, move_num); while (l < r && !LT(L.r[r].key, base)) r--; L.r[l] = L.r[r]; while (l < r && !LT(base, L.r[l].key)) l++; L.r[r] = L.r[l]; move_num += 2;

相关热词搜索:

热点文章阅读

版权所有 小龙文挡网 www.xltkwj.com