基于计算机程序设计的排序问题探讨

朱鹏飞

摘要：随着我国社会主义现代化建设的不断发展，我国的计算机信息技术得到了前所未有的提升，在现代社会生产与人们的生活中发挥着不可替代的作用。作为计算机程序设计中极为重要的组成部分，排序主要负责的是对某一项无规则数据元素或相关记录的有效排列，使其形成一种以某种关键字或参考排列的序列。本次研究中将着重对计算机程序设计的排序特点进行深入分析，介绍了常见的几类计算机程序设计排序方法，并探讨了计算机程序排序方法的有效选择，为计算机程序设计排序问题的解决提供参考。

关键词：计算机；程序设计；排序问题；排序方法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）33-0065-03

近年来，我国的软件开发技术得到了空前的提升，软件应用范围更加广泛，这很大程度上有赖于计算机程序设计的科学性。计算机程序设计对排序问题有着较高的要求，只有确保排序工作的有效性，才能够对计算机中存在的无序数据元素进行科学排列，满足设计人员的操作需求，进而提升数据、信息查找效率[1]。计算机程序设计方法多种多样，且容易受到多方面因素的影响，因此对计算机程序设计的排序问题探讨有着重要的实践意义与应用价值。

1 计算机程序设计排序问题相关概述

1.1计算机程序设计的排序概述

排序問题是计算机程序设计过程中极为重要的环节，相对复杂，一旦排序问题处理不得当，将直接影响到计算机程序设计效果。一般情况下，为了便于查找，计算机中的表往往按照关键字的排列顺序，供操作人员快速查找到所需信息，这能够在一定程度上提升查找效率，其对于计算机程序设计有着重要的意义[2]。由于待排序记录数量一般是不同的，因此其所采用的存储器也有着明显的差别，基于此可将计算机程序设计排序分为内部排序与外部排序两种形式，排序方法不同，其稳定性、算法复杂性也存在明显的差异性。目前，计算机程序设计都力图达到对任意给定问题进行低复杂设计进而达到简化算法的目的。简单来说，就是当某一给定问题存在多种算法时，要从其中选择一种复杂性最低的算法，对其进行相应的计算，这也是算法选择必须遵循的一个基本原则[3]。从另一方面来说，排序方法的多样性在一定程度上使计算机程序设计人员面临着更多的选择，因此，相关人员必须加强对计算机程序设计排序问题的认识，确保计算机程序排序的科学性与有效性，进而为计算机程序设计提供有效的参考。

1.2计算机程序设计排序基本特点

计算机程序的有效设计与计算机程序的稳定运行有着密不可分的联系，然而通过对计算机程序设计实际问题的综合分析，可以发现计算机程序设计中普遍存在排序问题，其对计算机程序设计效果有着较大的影响，因此，必须明确计算机程序设计排序问题的特点。

1.2.1排序的复杂性

通常，在进行计算机程序设计过程中，会涉及多方面的复杂内容，这就在一定程度上加大了数据排序操作的难度与复杂性，计算机程序设计排序问题更为复杂[4]。即使部分设计工作者制定了最佳的计算方案，其难度仍然较高，计算机程序设计的有效性难以保证。

1.2.2排序的不确定性

在具体的计算机程序设计工作中，往往会出现部分数据及记录插入的现象，其内容不容易确定，再加上其他不确定性因素，排序问题也会随之发生变化，造成了计算机程序设计排序的不确定性。

1.2.3排序的约束性

排序的约束性问题主要指的是各类数据资源信息之间的制约与影响作用，其对计算机程序设计的效果有着极为重要的影响，然而这种数据间的约束与制约关系又是普遍存在的，这也是当前我国计算机程序设计排序问题的一大特征之一。

1.2.4排序的多目标性

在数据排序的过程中，往往会出现一些未按照顺序排列的、杂乱无章的数据资源，这为计算机程序设计增加了难度，然而此类数据能够满足不同目标情况的多样化需求，因此，在对计算机程序设计的排序问题进行解决的过程中，要充分考虑目标的基本情况与相关设计标准，合理、科学的实施数据排序工作[5]，在排序过程中尽可能避免冲突，这种排序的多目标性也是计算机程序设计的重要特征。

通过对计算机程序设计排序问题基本特征的分析，可以发现计算机程序排序问题具有一定的复杂性，其会直接影响到计算机程序设计的效果。因此，要求计算机程序设计人员必须提升自身知识素养与技能水平，掌握科学、合理的排序方法，展开程序设计流程。

2 计算机程序设计排序的几种方法

基于当前的计算机程序设计实际，首先需要了解常用的几种计算机程序设计排序方法，并根据实际情况选取合理的排序方法，确保排序问题的妥善解决，提升计算机程序设计效率与实施效果，使计算机程序的各项功能能够有效实现，为相关行业的可持续发展提供必要的技术支持。

2.1选择排序法

选择排序法主要指的是对杂乱无章的需要重新排列的数据元素通过多种方式进行调整，达到合适的排序方式。通常，选择排序法需要实施多次综合对比分析，每次需在n-i+1（i=1，2，…n-1）中将最小的关键字记录选取为有序序列的第i个记录，选择排序又可分为简单选择排序、树形选择排序以及堆排序三种形式。（1）简单选择排序。在第i趟比较中，主要针对的是n-i关键字的对比，然后从n-i+1个相关记录中找到最小的关键字，将其与第i个记录实施交换。若数组中包含了n个元素，那么需要进行简单的选择排序，并实施n-1次的选择操作。可以发现，若数组本原本按照由小到大顺序排列，那么仅需移动0次便能够达到有效排列；而若数组原本呈现逆序排列，那么其应移动的次数不超过3（n-1）次。通常在进行选择排序时，需要对记录进行n（n-1）/2次对比，其时间复杂度为O（n2）。由此可以发现，选择排序关键词间需要进行大量的复杂操作，可以通过减少关键词对比，降低选择排序复杂性[6]。（2）树形选择排序，其是对简单选择排序的有效改进。该排序方法首先是n个关键字之间的比较，可以得出较小关键字（n/2），再次进行两两比较，反复上述操作，进而从中选出最小的关键字，该选择排序过程一般会采用n个节结点二叉树表示。N叶子结点完全二叉树深度可表示为[[logn2+1]]，次小关键字的选择则需要进行[[logn2]]次比较得出。该排序方法需要较大的辅助存储空间。（3）堆排法。堆排法能够有效弥补树形选择排序的缺陷，其能够将无需的序列排列成为一个堆，在排序过程中呈现出非递减或非递增有序队列形式，其最大时间复杂度为O（nlogn）。通常，单堆排序适用于n较大的文件，在n较小的排序中会存在较大的不稳定性。

2.2快速排序法

快速排序法在起泡排序法的基础上进行了新的改进，其能够通过一趟排序将需要排序的数据记录分割成为两个独立的部分，一部分所记录的所有关键字均少于另一部分关键字，基于此可以对这两部分进行相应的排序，从另一个角度来说，快速排序稳定性不佳。从起泡排序来看，其主要在交换的基础上进行。如在对数据进行由小到大的排列时，首先需要将相邻的数进行对比，如数组8，7，5，2，1，4，经过两两比较、交换，排序为7，5，2，1，4，8，最大的数字将会被沉埋，经过反复比较，最大的数逐渐沉底。N个数的比较次数为n-1。实践研究表明，冒泡排序在整个排序过程中仅需要一个辅助单元，其排序时间效率很大程度上与数据n相关。假设数据元素保持同一状态，那么正序冒泡法的比较次数则为n-1次，无需移动；其逆序冒泡法需要比较n（n-1）/2次，移动3n（n-1）/2次，从而计算出冒泡排序法的时间复杂度平均为O（n2）。通常在进行快速排序前，需要选取一个记录作为枢纽，并将比该记录小的关键字均放置于该记录前，相应的比该记录大的关键字则放于其后，便形成了以枢纽所在位置i为分界的两个子序列，采用递归算法实现快速排列。若待排序列仅包含了一个记录，那么可以认为该队列有序。若队列需要进行再次快速排序，那么需要对分割的子序列予以排序。從时间效率上来说，快速排序不失为当前计算机程序设计排序最有效的方法。若初始记录序列表现为基本有序或按照关键字进行有序排列时，那么可以通过快速排序将其转换为冒泡排序。

2.3插入排序法

所谓插入排序，主要指的是在已经排列好的序列中加入一个新的记录，进而得到一个新的有序表。通常，在进行插入排序时，首先需要明确插入的位置，在首址位置建立监视哨，避免出现出界现象。插入排列采用的是分趟操作的方式，通常，在对第i趟进行排序时，需要从i-1前查询合适的位置插入，当对n个记录进行排序时，则需要n-1趟插入，其属于简单的排序方法。若排列的n个记录为正序，那么仅需要几次比较即可，为n-1次，且无需进行任何移动操作。假设其处于最差状态下那么其所需移动的记录为（n+2）（n-1）/2次，次数为（n+4）（n-1）/2次[7]。一般情况下，记录排列多是凌乱无序的，可以综合其最差与最好的状况均值，并得出其时间复杂度为O（n2）。通常，若记录n值较小，那么采用直接插入排序法则相对简单，且容易实现，但不适用于n较大的情况。基于上述情况又出现了2路插入排序，该方法尽管不能够避免移动，然而其能够在一定程度上降低移动次数，希尔排序对其他排序方法进行了新的改进，提升了时间效率，其能够将待排序记录分割成为多个子序列实施排序，在这个过程中，关键字能够实现跳跃移动，当其形成一定的排序后，再进行1增量插入排序。

3 计算机程序设计排序方法的有效选择

排序方法的选择对计算机程序设计效果有着极为重要的影响。然而，无论是选择排序法、快速排序法还是插入排序法其时间复杂性都与n有着一定的联系，即排序方法的选择应考虑n的大小。通常，若n较小，那么一般适于选择直接插入法或直接选择法，这两种排序方法需要进行多次移动，因此，在需要记录大量信息的条件下，可以采用直接选择排序法。而若n较大，那么则不适于选择需要较多移动次数的排列方法，应尽可能选用时间复杂度小的排序法，如快速排序法、堆排序等[8]，这几种排序方法也有着各自不同的特征，若实施的内部排序，那么则可优先选用快速排序法，其能够实现对任意分布关键字的有效排序，且能够确保所用的平均时间最少。另外，给定数值文件的状态也与排序方法的选择有着极为重要的联系，若其初始状态显示为正序排列，那么可以选择直接插入法或冒泡排序法，部分排序需要对关键字进行相应的比较，然后再进行转移，采用二叉树排序法对其进行描述。若n较小，且其所记录的关键字也较少，可以实施分解，将其转变为子序列进行排序，有利于排序问题的有效解决。

4结束语

新时期，我国的计算机信息技术也取得了新的进展，计算机程序设计的排列问题逐渐成为计算机领域的研究重点，排序方法不同，其能够解决的问题也有着明显的差异性，各种排序方法既有着自己明显的优越性，又存在着一定的缺陷，因此，要加强对排序思想、方法及效率的分析与比较，针对具体的问题，给予相应的排序方法，确保计算机程序设计的实现，为工作与生活提供帮助。

参考文献：

[1] 吕雪. 计算机程序设计中基于任务驱动模式的冒泡排序算法教学设计[J]. 通讯世界， 2015（15）：261-263.

[2] 邹汪平， ZOUWang-ping. 基于能力导向的高职计算机程序设计类课程案例-任务驱动教学模式研究[J]. 通化师范学院学报， 2015（6）：74-77.

[3] 宛西原， 汪霞. 非计算机本科专业计算机程序设计课程的改革思考[J]. 计算机工程与科学， 2014， 36（s1）：56-59.

[4] 韩松. 以应用为导向的计算机程序设计语言类课程教学探讨[J]. 无线互联科技， 2014（10）：231-232.

[5] 王帅， 喻歆， 何嘉. 基于MPI和OpenMP的排序算法并行优化研究[J]. 成都信息工程大学学报， 2016（3）.

[6] 张乐成， 靖宇， 邵梅. 基于程序设计课的计算机模拟实验教学实践与探讨[J]. 福建电脑， 2011， 27（4）：204-205.

[7] 李镔洋， 李博涵， 王庆全. 关于初学者学好计算机程序设计语言的几点探讨[J]. 硅谷， 2013， 14（7）：191-192.

[8] Zhu Y， Wang J， Qu B. Multi-objective economic emission dispatch considering wind power using evolutionary algorithm based on decomposition[J]. International Journal of Electrical Power & Energy Systems， 2014， 63（12）：434-445.