探讨程序设计语言中排序算法的教学

摘 要：目前排序算法的动态演示多数采用简单的数字输出方式，为了清晰而容易地理解程序设计语言中排序算法的思想，更好地掌握排序算法。本文引入立方柱形方式动态演示了排序算法内部交换数据的过程对排序算法的教学进行探讨。

关键词：排序；元素；算法

中图分类号：TP316.2 文献标识码：B 文章编号：1002-7661（2013）34-029-02

一、引言

排序就是将线性表中的各元素按关键字从小到大（或从大到小）的顺序重新排列。在本文里，把作为排序依据的关键字称为排序码。排序过程一般都涉及到排序码的比较和元素的移动这两种基本操作。排序算法的执行时间通常用这两种基本操作的执行频度来衡量。在程序设计基础教学中，排序算法不但是一种基本算法而且还是一种常用的算法，是学生必须掌握的内容。从我多年的程序设计教学中发现往往书中的排序算法的文字描述对学生来说很难理解。程序语言的描述更是不知其所指，这对学生来说很大的打击了他们学习的积极性，也使得他们很难真正的掌握排序算法，并在实际应用中发挥作用。本文就这一现象问题将排序算法用VC++设计成动态的排序效果生动形象地演示学生看，有助于学生理解并掌握，增强学生学习排序算法的积极性。

本排序动态演示设计的思想是：以一种排序算法作为范例，动态的演示一组数据在这个算法思想下的变化过程，并在动态演示过程中随时可以调整排序速度以便给学习者有思考的过程，通过动态的演示让学习者清晰的看到算法的思想。这种动态的演示算法的过程可以推广到其他排序算法中去，有了这个动态过程的演示，学生就可以轻松的掌握各种算法的思想，并在程序设计的过程中很好的利用。

二、排序算法

常见的排序算法有快速排序、希尔排序、堆排序、选择排序、起泡排序、折半插入排序、直接插入排序、归并排序，这些排序算法都各有其优缺点。本文将对起泡排序、选择排序这两类进行探讨。

1、起泡排序

起泡排序算法的基本思想是：在元素中依次比较两个相邻元素的排序码，若前者比后者大则交换，若前者比后者小则保持不变。先将第一个排序码与第二个排序码比较，然后是第二个与第三个比较，直到倒数第二个与最后一个排序码。比较一轮结束之后，排序码大的记录均向后移动。然后开始新一轮的比较，知道一轮比较下来，不再有排序码的交换发生为止。整个过程就有点像水中的气泡上升的过程，轻的往上浮，重的向下沉，所以这个算法也叫起泡排序法。算法的步骤如下：

（1）假设要排序的数列为A[1]……A[N]，我们把相邻的两个数两两进行比较。即把A[1]和A[2]比较，对比完后把A[2]和A[3]进行比较，……直到A[N-1]和A[N]比较完为止。在相邻的两个数两两进行比较的过程中，如果前面的一个数比后面的一个数大，则把这两邻的两个数交换，也就是说，我们把较小的数放在前面，把较大的数调到后面。即，如果在一次比较中，如果A[1]比A[2]大的情况下，把A[1]和A[2]交换，……以此类推，直到一轮A[N-1]和A[N]比较完。

（2）再次重复（1），直到相邻两数之间不再发生交换为止。

2、简单选择排序

简单选择排序算法的基本思想是：从所有元素中选出排序码最小的元素，将它与A[0]交换位置；然后，在A[1]～A[N]中选出排序码最小的元素，将它与A[1]交换位置；依次做下去，在进行了N-1次选择后排序过程结束。这种排序算法比较的次数与前一种排序算法一样多，但是交换次数要比起泡排序算法少，效率较高。

三、演示方法

1、传统方式的演示方法

目前大专院校教师在对语言程序设计中排序算法的内容进行讲授时一般采用静态数字输出方式，如图1所示。这种方法对于描述排序算法中交换数据的过程不够形象生动。

图1 传统方式的排序演示方法

2、立方柱形的动态演示方法

（1）设计原理

本排序算法动态演示程序是在VC++6.0集成环境下实现，基于对话框类型的MFC应用程序。为了直观清楚地表现起泡排序与选择排序的排序过程，程序设计的主界面如图2所示。

图2 排序算法动态演示程序主界面

程序主界面是一个对话框，包含控制区，演示区和说明区三个部分。

控制区位于主界面的上方，主要由下拉组合框控件，按钮控件，滑动控件以及静态文本框控件组成。下拉组合框控件供选择产生多少个随机数进行动态排序演示，按钮控件用来控制动态排序演示的开始，滑动控件用来控制演示速度，在需要仔细查看演示过程的时候，可以将滑动块移到最左边演示。

演示区位于主界面的中间，由上下两个绘画窗口（静态文本框控件）组成，负责将排序中的数据以立方柱形绘制出来，而不是简单输出我们通常熟悉的1、2、3等数字符号，显得更为直观，比较有动态演示效果。

说明区位于主界面的右边，由上下两个静态文本框控件组成，是对描述排序算法动态演示的简单说明。

（2）主要实现过程

首先创建一个基于对话框类型的MFC应用程序SortingDemo，在主对话框上添加所需要的控件。然后，在对话框CSortingDemoDlg的初始化函数OnInitDialog末尾加入控件的初始化代码。

在CSortingDemoDlg.h中的类SortAlgoWindow里定义m_wndSortAlgo1和m_wndSortAlgo2的2个实例，分别实现对起泡（升序）排序和简单选择（升序）排序的动态演示。

类SortAlgoWindow是从CWnd派生的一个窗口类，重载WM_PAINT消息，OnPaint方法里面实现更新后的数组元素的绘制。

类SortAlgoWindow的UpdateSoringData方法会更新并重绘排序中的数据。

void SortAlgoWindow：：OnPaint（）

{ CPaintDC dc（this）； // device context for painting

// TODO： Add your message handler code here

// Do not call CWnd：：OnPaint（） for painting messages

// 绘制面板底色

// 根据排序中的数组元素，绘制立方柱

// 用红色绘制发生交换的数据1

// 用蓝色绘制发生交换的数据2 }

按钮控件是用来控制排序动态演示的开始，通过创建2个线程实现起泡（升序）排序和简单选择（升序）排序的排序过程，并将排序过程以立方柱形显示到对应的显示控件中。

void CSortingDemoDlg：：OnBnClickedStart（）

{ AfxBeginThread（BubbleSortProc， this）；

AfxBeginThread（SelectSortProc， this）； }

（3）程序运行

图3是程序运行时排序过程中的一个截图，从图中可以看到，在起泡（升序）排序过程中，相邻的红色，蓝色2个元素进行了交换，较大的元素向后移动。而在简单选择（升序）排序过程中，较小的（蓝色）数据被排到了最前面。

图3 排序算法动态演示程序开始

所有元素按照升序方式排序结束后的最终运行界面如图4所示。

图4 排序算法动态演示程序结束

四、结语

我们在进行程序设计中排序算法内容的教学时采用本文中立方柱形方式的动态演示方法讲授，由于它的直观性能够使得让抽象的内容不再难以理解，必然能较好地带动学生学习排序算法的热情，从而产生良好的效果。

参考文献：

[1] 谭浩强.语言程序设计（第一版）.华大学出版社，2005.

[2] 薛超英.数据结构（第一版）.中理工大学出版社，2000.

[3] 孙义欣，许 涛，韩淑芹.潍坊教育学院学报，2008.12.