没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源C/C++可视化的简单数组实现排序

可视化的简单数组实现排序

简单排序算法

需积分: 11 7 下载量 170 浏览量 2017-05-30 14:34:59 上传评论收藏 240KB DOCX 举报

温馨提示

试读

22页

通过学习数据结构中的一些简单的排序算法，尝试编写此程序，并尽量以可视化的形式展现~

资源推荐

资源详情

资源评论

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称：实验 3——简单数组实现排序

学生姓名：XXXXNB

班级：XXXXXXXX

班内序号：

学号：XXXXXXXX

日期： 2016 年 XXXXXXX

1．实验要求

使用简单数组实现下面各种排序算法，并进行比较。

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

第 1 页

北京邮电大学信息与通信工程学院

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移

动次数（其中关键字交换计为 3 次移动）。

//3、对于这三类数据，比较上述排序算法中不同算法的执行时间，

精确到微秒（选作）

4、对 2 和 3 的结果进行分析，验证上述各种算法的时间复杂度

编写测试 main()函数测试线性表的正确性。

2. 程序分析

在题目中要求测试不同的数据，可以手动输入待排序元素。我在编程时为了界面的简

洁易于监控，便选择了在主程序中把数组写好放入主程序里。同时为了方便每种算法

的比较，我将所有的函数包装为一个类，方便运行并监控。比较遗憾的是，我没有做

算法运行时间的相关程序，为了弥补这种缺陷，我选择了将界面做的更人性化一些。

2.1 存储结构

采用数组进行顺序存储结构

示意图如下:

2.2 关键算法分析

第 2 页

北京邮电大学信息与通信工程学院

核心算法思想：

1. 利用教材讲述的基本算法思想，实现其中五种排序算法，统计其运行相关数据。

2. 将五种排序函数封装到一个类中，使得程序代码可读性、结构更加优化。

排序算法分析：

1.插入排序算法

插入排序的思想是：每次从无序区取一元素将其添加到有序区中。

a.直接插入排序

C++描述如下，其中形参 a[]为待排序数组，n 为待排序元素个数

同时添加两个变量 move,compare 用于记录整个排序过程中的比较次数以及移动

次数

void Sort::DirectInsertSort(int a[], int n)//直接插入排序

{

int k;

int move = 0;

int compare=0;

for (int i = 2; i <= n; i++)//第一个定然为有序，出现两个数据时开始进行排序

{

if (a[i] < a[i - 1])

{

a[0] = a[i];

move++;//元素赋值移动+1

for (int j = i - 1; j > 0 && a[0] < a[j]; j-- )

{

a[j + 1] = a[j];

move++;//移动+1

compare++;//for 条件中比较+1

k = j;//记录查找出的位置

}

a[k] = a[0];

move++;//元素赋值移动+1

第 3 页

北京邮电大学信息与通信工程学院

}

compare++;//if 比较 n 大小+1

}

cout << "移动次数" << move << endl;

cout << "比较次数" << compare << endl;

}

b.希尔排序

希尔排序，设待排序对象序列有 n 个元素，先取 d<n,比如 d=n/2，作为间隔，

将全部对象分为 d 个子序列，对每一个子序列分别进行直接插入排序，然后缩

小间隔 d，即减少子序列个数

例如取 d=d/2，重复子序列的划分和排序工作，直到取 d=1，仅有一个子序列

为止（ps：本质上仍为直接插入排序的改进）

C++描述如下，其中形参 a[]为待排序数组，n 为待排序元素个数

同时添加两个变量 move,compare 用于记录整个排序过程中的比较次数以及移动次数

void Sort::ShellInsert(int a[], int n)//希尔排序，本质上为直接插入排序的改进

{

int k;

int move = 0;

int compare = 0;

for (int d = n / 2; d >= 1; d = d / 2)

{

for (int i = d + 1; i <= n; i++)//前 d 个元素是每个子序列头部，为初始有序区，从 d

+ 1 开始循环

{

if (a[i] < a[i - d])//并不是单独分别对各个子集分别排序，而是依次从每个子集第二

个元素排起

{

a[0] = a[i];

move++;//赋值移动+1

for (int j = i - d; j > 0 && a[j] > a[0]; j = j - d)

{

第 4 页

北京邮电大学信息与通信工程学院

a[j + d] = a[j];

move++;//元素后移+1

compare++;//for 循环中条件比较+1

k = j;

}

a[k] = a[0];

move++;//元素赋值移动+1

}

compare++;//if 中比较+1

}

cout << "移动次数" << move << endl;

cout << "比较次数" << compare << endl;

}

//希尔排序利用了直接排序的两个特点：1.基本有序直接插入最快 2.记录个数很少的无序序列，直

接插入也很快。

//希尔排序是不稳定的排序算法，时间复杂度是实验测得的

2.交换排序

a.冒泡排序

在基本的冒泡排序上进行改进：简单的冒泡排序每一趟只添加一个进入有序区，

若无序区存在有序的元素仍需比较，效率低，改进后的冒泡排序将每一趟最后

一次交换的位置作为下一次起泡无序区的末尾，这样会减少开销

C++描述如下，其中形参 a[]为待排序数组，n 为待排序元素个数

同时添加两个变量 move,compare 用于记录整个排序过程中的比较次数以及移动次数

void Sort::ImprovedBubbleSort(int a[], int n)//改进的冒泡排序

{

int move = 0;

int compare = 0;

第 5 页

剩余21页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

看星星的许愿者

粉丝: 90
资源: 6

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

可视化的简单数组实现排序

各种排序算法的可视化比较_C++_

可视化排序

用数组实现的快速排序算法

各种排序算法可视化

可视化展示选择排序算法实现效果

详解数组Array.sort()排序的方法

基于Qt5-实现九大排序算法的代码汇总

数据结构课设排序算法的可视化演示（QT+C++）

3种排序算法可视化程序 c++ 算法

QT5.5或QT5.6与echarts实现动态图表例子

利用java实现排序类简单排序过程的可视化

C#简单的排序算法可视化程序

sort：数组排序可视化器

matlab 矩阵数组 矩阵-排序和翻转 算法开发、数据可视化、数据分析以及数值计算 Matlab课程 教程 进阶

Sort-Visualizer:用C ++和SFML进行排序算法的可视化

vc++6.0 MFC实现排序算法

排序动态演示程序winform

继承QlistWidgt，实现拖拽排序功能

七种排序算法动态演示软件

几种常见的排序动态图+代码

基于C语言和EasyX实现的玫瑰花图形界面

实验一——排序

各动态图示排序算法（冒泡、快排、堆排）

qtc++排列组合实现

SortingSounds:可视化三种不同排序算法的Java应用程序

D3.js的基础部分之数组的处理数组的排序和求值(v3版本)

sorting.js:可视化JavaScript中的排序算法

Visual-Sorting-App：React应用程序，以可视方式演示数组排序算法（进行中）

array-sorts-visualizer:一个React Web应用程序，可视化用JavaScript编写的数组排序算法

最新资源

matlab 矩阵数组矩阵-排序和翻转算法开发、数据可视化、数据分析以及数值计算 Matlab课程教程进阶