计算机程序设计排序方法研究

朱莹莹

（河南师范大学，河南 新乡 453007）



计算机程序设计排序方法研究

朱莹莹

（河南师范大学，河南 新乡 453007）

摘 要：在计算机程序设计的算法中，存在多种排序方法。学习和研究各种排序方法是计算机工作者的重要课题之一。排序作为一种重要的算法，就是将一个数据记录的随意排序，重新排成一个按关键字排序的序列。文章将会介绍计算机程序设计中几种常用的排序方法，并对其各种性能进行分析。

关键词：选择排序；插入排序；合并排序；快速排序；时间复杂度

为了查找方便，通常计算机中的表是按关键字排列有序的，因为这样有序的顺序表可以采用查找效率较高的查找方法，提高查找的速度。因此，排序是计算机程序设计中重要的操作。因为待排序记录的数量往往是不同的，排序时使用的存储器不同，可将排序方法分为两大类，内部排序和外部排序。不同排序方法的性能往往存在着很大的差别，有的排序方法是稳定的，而有的却不稳定，并且算法复杂性的高低有很大的差别。不言而喻，因此对任意给定的问题，设计出复杂性尽可能低的算法是设计算法时追求的一个重要目标。另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是选用算法时遵循的一个重要准则。因此，算法的复杂性分析对算法设计或选用有着重要的指导意义和实用价值［1］。本文除了给出了每种排序算法在进行排序时所依据的原则，还对其进行了复杂度的分析以及优缺点的评价。

1　各种排序方法的分析

1.1 选择排序

选择排序（Selection Sort）需要进行多趟比较，每一趟在n-i+1（i=1，2，...，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。其中，又分为简单选择排序，树形选择排序，堆排序。

简单选择排序，第i趟要通过n-i次关键字之间的比较，从n-i+1个记录中选取关键字最小的记录，并和第i个记录进行交换。对含有n个元素的数组，再进行简单选择排序，需要进行n-1次的选择操作。通过分析，能够得出，当一个数组本来就从小到大有序排列时，记录只需移动0次，而如果记录是逆序排列的话，所需移动的次数最多为3（n-1）次。而进行选择排序时，记录都需要进行n（n-1）/2次比较，一般情况下，简单选择排序的时间复杂度为O（n2）。由上可知，选择排序关键词之间的比较操作较多，要想进行改进，可以减少关键词之间的比较。

树形选择排序（Tree Selection Sort）是对简单选择排序一种改进的方法。它的思想是n个关键字先两两比较。这样会得出个较小的关键字，然后再进行两两比较，这样一直重复进行能够选出最小的关键字。这个过程通常会用含有n个节结点的完全二叉树表示。含有n个叶子结点的完全二叉树的深度是，选择次小关键字需要进行次比较，由此可以得出树形选择排序的时间复杂度。这种方法的缺点是辅助存储空间较多。另一种选择排序的方法，堆排序（Heap Sort）可以弥补这种缺点，它只需一个记录大小的存储空间。排序的过程就是将一个无序的序列建成一个堆，也称作“筛选”。堆有“大顶堆”和“小顶堆”，排序过程可以使记录序列按非递减或非递增有序队列。堆排序在最坏的情况下，时间复杂度为O（nlogn）。单堆排序对n较大的文件进行排序有效，当n较小时并不适合，并且堆排序是一种不稳定的排序方法。

1.2 快速排序

快速排序（Quick Sort）是对起泡排序方法的一种改进。它的基本思想是，通过一趟排序将代排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字少，则可分别对这两部分记录继续进行排序，以达到整个序列有序［2］。快速排序是一种不稳定的排序方法。

首先介绍一下起泡排序（Bubble Sort），它是一类基于“交换”进行排序的方法。以将数据从小到大排序为例，其基本思路就是每次将相邻的两个数进行比较，每一次排序可将最大的数“沉底”。例如，若有6个数，8，7，5，2，1，4。经过第一趟交换为7，5，2，1，4，8，最大的数8已经“沉底”。每一趟的比较都是使该趟最大的数“沉底”。如果有n个数需要进行n-1趟比较，在第j趟中需要进行n-j次比较。通过对冒泡排序法的排序过程进行分析，冒泡排序在排序过程中只需要一个辅助单元，其空间复杂度为O（1）。它的时间效率与数据的n有关，若数据元素的状态保持不变，正序冒泡法的比较次数为n-1，移动次数为0，逆序冒泡法的比较次数为n（n-1）/2，移动次数为3n（n-1）/2［3］。通过分析可知冒泡排序法的平均时间复杂度为O（n2）。

快速排序在排序前需要任意选取一个记录作为“枢纽”。通常情况下选取第一个记录，然后将使所有关键字比它小的记录都放在它的位置之前，所有关键字比它大的记录都放在它之后。这样可以将序列分为两个子序列，分界线是“枢纽”所在的位置i。整个快速排序的过程可以用递归算法来实现，当待排序列中只含有一个记录时，则该队列一定是有序的。否则，需要再次进行快速排序，即对分割的两个子序列进行排序。例如初始序列为49，38，65，97，76，13，27，49。选择第一个关键字为49，经过一次快速排序后变为｛27，38，13｝49｛76，97，65，49｝，然后再分别对分割的两个子序列进行排序，直至排序完成。就平均时间而言，快速排序是目前最好的一种排序方法。当初始记录序列按关键字有序或基本有序时，快速排序将蜕化为冒泡排序。

1.3 插入排序的分析

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增1的有序表。由于需要查找插入位置，为了避免出界，通常要在首址设置监视哨。插入排序也是分趟操作，在第i趟排序时，则从i-1往前搜索来查找合适的插入位置，对n个记录进行排序，整个排序过程需要进行n-1趟插入。直接插入排序是一种最简单的排序方法。当被排列的n个记录序列为正序时，需要的比较次数最少，仅需n-1次，并且不需要移动记录。最差的情况下需要移动记录（n+2）（n-1）/2次，移动次数为（n+4）（n-1）/2。通常情况下，记录是杂乱无章地排列着，可以取上述分析的最差和最好情况下的平均值，易得时间复杂度为O（n2）。

直接插入排序在记录n的值不大时，易于操作，并且很容易实现，但当n很大时，并不适合使用，由此出现了其他改进的排序方法。从减少比较次数方面考虑，出现了折半查找。2-路插入排序，可以减少排序过程中的记录的移动次数，但不能避免移动，且所需的辅助存储空间增多。表插入排序可以通过改变存储结构，避免移动。希尔排序（Shell’s Sort）与上面所述的几种改进的插入排序方法相比，在时间效率上又有较大改进。它不是直接对全体记录进行排序，而是将待排记录分割为若干个子序列进行排序。子序列的构成也不是简单的“逐段分割”，其中的记录都是相隔一定的“增量”。因此在进行一趟插入排序时，关键字的记录可以跳跃式的移动。当序列已经基本有序时，直至最后才进行一次增量为1的插入排序。由于增量序列并且影响着希尔排序的时间复杂度，增量序列的选择是一个复杂的问题。但是希尔排序从使待排序列按关键字“基本有序”和使每次排序时n的取值尽量小两个方面，对直接插入排序进行了改进。

1.4 合并排序

合并排序（Merging Sort）是一种运用分治策略的思想的算法，它将n个待排序的记录分成大小大致相同的两个集合，分别对两个子集合进行排序，最后将各个排好序的子集合合并成按要求排序的集合，整个算法要通过递归调用实现。具体实现过程是：将待排元素一分为二，每个子集继续递归拆分直到分解到仅一个元素为止，然后两合并为一个有续集即完成了排序。因此通过合并排序算法进行排序，在最坏的情况下时间复杂度的计算：

通过解这个方程可以得出T（n）=O（nlogn）。与快速排序相比，合并排序最大的特点就是一种稳定的排序算法。

2　排序方法的比较与总结

简单排序的平均时间为O（n2），最坏情况下也是O （n2），需要辅助的存储空间是O（1）。快速排序的平均时间是O（nlogn）。最坏情况是O（n2），辅助存储空间是O （logn）。合并排序的平均时间是O（nlogn），最坏情况下是O（nlogn），需要的辅助存储空间是O（n）。通过分析不难得出，当待排序的n的值较大时，宜采用合并排序的排序算法，所需时间较省，但是需要的辅助存储空间较多。快速排序在平均性能上需要的时间最少，但是在最坏的情况下需要的时间较多。当待排序的记录“基本有序”或者n的值不大时，直接插入排序较简单，可以认为是最佳的排序方法。它经常和快速排序，合并排序等其他的排序方法一起配合使用。

3　结语

通过对几种排序方法的分析和比较，不难得出每一种排序方法就其全面性能而言，很难判断出哪一种方法最好。不同的排序方法有不同的适应场合，应根据具体地实际情况选择合适的排序方法。在一个程序设计中，方法的选择可以不局限于一种，为了达到最好的效果，可以多种排序方法配合着使用。在学习每一种排序方法的思想与原理时，深入了解每种算法的精髓，有助于创造出新的合适的算法。

［参考文献］

［1］王晓东.计算机算法设计与分析［M］.4版北京：电子工业出版社，2012（2）：15-17.

［2］严蔚敏.吴伟民.数据结构，C语言版［M］.北京：清华大学出版社，2007.

［3］张健.计算机程序设计中的排序问题探讨［J］.计算机光盘软件与应用，2014（14）:169-170.

Research of Computer Programming Sorting Methods

Zhu Yingying
（Henan Normal University，Xinxiang 453007，China）

Abstract:In computer programming，algorithms，there are various sorting methods. Learning and research various sorting methods is an important issue for computer workers. As an important sorting algorithm is a data record of arbitrary sorting，re-arranged in a sequence ordered by keywords. In this paper，a computer program will introduce the design of several commonly used sorting method，and to analyze the various properties.

Key words:choose sort；insertion sort；merge sort；quick sort；the time complexity

作者简介：朱莹莹（1995-），女，河南周口；研究方向：计算机算法。