数据结构(C语言版)实验指导书(2)

图4 打印扬辉三角程序的流程图

实验四 排序（Sorting）

排序是将一个数据元素（或记录）的无序序列，重新排列成一个按排序关键字递增（或递减）的有序序列的过程。在计算机软件设计中，排序占有相当重要的地位。排序分为内排序和外排序。我们只讨论内排序。内排序主要的排序算法有：插入排序、交换排序、选择排序等。排序算法有稳定和不稳定之分。排序的时间开销主要是指执行算法中关键字的比较次数和记录移动的次数。

一、 实验目的

掌握常用的几种内部排序算法。理解各种内部排序法的基本思想和特点，熟悉内部排序法的排序过程，记住各种算法的是时间复杂度，以便在实际应用中，根据实际问题的要求，选择合适的排序方法。

二、 实验内容

选用直接插入排序算法编写程序对下列记录进行排序。有兴趣的同学可以多选择几种排序算法进行比较。

49 38 65 97 76 13 27 49 55 04

三、实验原理

假设待排序的记录存放在数组R[n]中，初始时R[1]自成为一个有序区，无序区则是R[2]到R[n-1]，然后依次将R[2]，R[3]，…，插入到有序区中，直至i = n-1时，将R[n-1]插入到有序区为止。具体做法是将待插入记录R[i]的关键字依次与有序区中记录R[j]（j = i-1，i-2，…，1）的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可。另外，我们将R[0]作为监视哨来减少测试循环条件的时间。

直接插入排序算法的流程图如图9所示。

四、思考题

通过分析，判断直接插入排序算法是稳定的还是不稳定的？

图9 直接插入排序算法流程图

附录1：在Visual C++ 6.0中建立、编译和运行程序 确认系统已经安装Visual C++ 6.0，以下简称VC6.0。

1、启动VC6.0，选取菜单File->New，出现如下图所示的对话框。

2、选取“Project”属性单中的“Win32 Console Application”， 在“”中输入工程要保存的位置为“E:\”（不输入引号，以后同），最后在“Project name”中输入工程名“Graph”（这里假设为Graph），则在“Location”中会显示“E:\Graph”，最后按下“OK”按钮。

3、出现如下图所示的对话框。选取“”， 按下“”按钮。

4、出现如下图所示的对话框，该对话框显示了工程的一些特征。 按下“OK”按钮。

5、按下“OK”按钮，则出下如下图所示的界面。

6、用鼠标单击“Graph classes”左边的“+”号，则出现“Globals”，同样单击“Globals”

左边的“+”号，则出现main()。单击main()，则在右边视图中出现主函数main()。注意：要选取ClassView。如下图所示。

7、在“#include "stdafx.h"”下，输入代码，行，否则编译出现错误。如下图所示。

8、最后按下工具栏中的运行程序，或者选取“Build”菜单中的“Execute Graph.exe”，或者按下“Ctrl+F5”键（按住Ctrl键不放，同时按下F5键）运行程序。如下图所示。

附录2：在Turbo C 3.0中建立、编译和运行程序

确认系统已经安装Turbo C 3.0，以下简称TC3.0。

1、 启动TC3.0，选取菜单File->New，则可以编写新的C源程序；选取菜单File->Save，可以保存编写好的C源程序；选取菜单File->Open可以装入已经编写好的C源程序；选取菜单File->Quit退出TC3.0环境。如下图所示。

2、 程序编写好后，选取菜单Run->Run编译程序，如果没有错误，则进行链接，如果链接成功，则运行程序；若有错误，则更正错误后，再重复上述过程。如下图所示。

3、 程序正常运行后，如果要查看程序结果，选取菜单Run->Run则可以查看程序结果，然后按任意键返回TC3.0环境中。如下图所示。