程序设计排序算法分析

冯毅宏 杨英翔 刘冬莉 何彤

摘 要：排序算法是计算机程序设计的一个重要内容，对排序算法的分析与研究具有广泛的应用价值。本文介绍了常见的排序算法，并通过对比分析，对各种排序算法从算法评价角度给出了综合评价。

关键词：排序算法；内部排序；对比分析；算法评价

排序是程序设计的常见问题，选择合理高效的排序算法是数据处理的最重要的研究问题之一。排序算法的功能是将一个由一组数据元素或记录组成的无序序列，重新排列成一个按关键字有序的序列[1]。有序序列可有效地提高记录的查找效率。

1 排序算法分类

1.1 内部排序

内部排序是指待排序列完全存放在内存中所进行的排序过程，适合规模不太大的数据元素序列。内部排序可分为五类： 插入排序、交换排序、选择排序、归并排序和分配排序。

1.2 外部排序

外部排序是指待排序的序列无法一次装入内存，需要在内存和外存之间进行多次数据交换，从而达到对序列中全部数据元素的排序。外部排序可将待排序序列分解成几段能够一次性装人内存的待排序部分，然后对每一小段采用内部排序，再对已经排序的各子段进行归并排序。即外部排序转化为内部排序。因此需对内部排序进行更深入的研究分析。

2 常见的排序算法

2.1 插入排序

插入排序每次将一个待排序的数据元素，插入到前面已经排好序的序列中适当位置，使序列依然有序，直到待排序数据元素全部插入完为止。插入排序包括直接插入排序、折半插入排序和希尔排序。

（1）直接插入排序：将无序序列中的第一个数据元素依次插入到有序序列的合适位置，使有序序列仍然有序。

（2）折半插入排序：在有序序列中用折半法（二分法）查找待插入数据元素的位置。将处于有序序列中间位置数据元素的关键字和待排序数据元素的关键字比较，便把可插入的区间缩小一半，故称为折半。折半插入排序仅减少了关键字间的比较次数，但数据元素的移动次数不变。

（3）希尔排序：先 取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1组。所有距离为d1的倍数的记录放在同一组中。先在各组内进行直接插入排序，然后取第二个增量d2

2.2 交换排序

交换排序是指通过在数据元素之间互相交换逆序元素而进行的排序。交换排序包括冒泡排序和快速排序。

（1）冒泡排序：通过将相邻的数据元素进行比较，若逆序则交换，逐步将无序序列处理成为有序序列。每一趟交换排序都会增加一个元素到有序区，整个冒泡排序过程最多需要进行n-1趟排序。

（2）快速排序：通过一趟排序将待排序的数据元素分割成独立的两部分，其中一部分数据元素的关键字均比另一部分数据元素的关键字小。则可分别对这两部分元素继续进行排序，以达到整个序列有序。

2.3 选择排序

选择排序是每一趟从待排序的数据元素中选出关键字最小（或最大）的一个元素，插入已排序序列的最后，直到n个数据元素全部插入已排序序列中。选择排序包括简单选择排序、树型选择排序和堆排序。

（1）简单选择排序：从无序的序列中选取一个关键字最小的数据元素存放到有序序列中指定的位置。

（2）树型选择排序：又称为锦标赛排序，是按锦标赛思想进行选择排序的方法。先对n个数据元素的关键字进行两两比较，然后在其中的（n/2）个较小者间再进行两两比较，如此往复，直至选出最小关键字的数据元素为止。这个过程可用一棵n个结点的完全二叉树来表示。

（3）堆排序：堆是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。这种堆中根结点（称为堆顶）的关键字最小，称之为小根堆；反之，则称之为大根堆。堆排序的算法是：将当前无序区调整为一个大根堆（或小根堆），选取关键字最大（或最小）的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

2.4 归并排序

归并排序是将两个或两个以上的有序序列合并成一个新的有序序列。归并排序包括二路归并排序和多路归并排序。

（1）二路归并排序：将两个有序序列合并成一个新的有序序列。先从两个有序序列中分别取第一个数据元素比较，关键字小（或大）的数据元素排入新的有序序列，同时在对应原序列中删除该数据元素；然后再从两个有序序列中分别取第一个数据元素比较，如此循环；当有一个序列为空时，则直接将另一个序列的数据元素依次取出即可。

（2）多路归并排序：将多个有序序列合并成一个新的有序序列。通常用于外部排序。

2.5 分配排序

分配排序的排序过程无须比较关键字，而是通过分配和收集过程来实现排序。分配排序包括箱排序和基数排序。

（1）箱排序。

箱排序是设置若干个箱子，依次扫描待排序的数据元素R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里（分配），然后按序号依次将各非空的箱子首尾连接起来（收集）。

（2）基数排序

基数排序的算法是：一个逻辑关键字可以看成由若干个关键字复合而成的，可把每个排序关键字看成是一个d元组，即例如由关键字K由d个关键字（K0，K1，…，Kd-1）组成，排序时先按K0的值从小到大（或从大到小）将记录分配到r个盒子中，然后依次收集这些记录，再按K1的值分配到r个盒子中，如此反复，直到按Kd-1的值分配后收集起来的序列，便是完全排序的状态，其中r称为基数。基数的选择和关键字的分解法因关键字的类型而异。基数排序分为最高位优先法和最低位优先法。

3 算法评价

3.1 稳定性

在待排序的序列中，若存在元素值相同的记录，经过排序后，这些元素的相对次序不变，那么此算法为稳定的。冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法；选择排序、快速排序、希尔排序、堆排序是不稳定的排序算法。

3.2 时间复杂度

时间复杂度是指执行算法所需要的计算工作量[3]。按平均情况下时间复杂度将排序分为四类：（1） 平方阶（O（n2））排序：一般称为简单排序，如冒泡排序、简单选择排序和直接插入排序。（2） 线性对数阶O（nlgn）排序：如快速排序、归并排序和堆排序。（3） O（n1+￡）阶排序：￡是介于0和1之间的常数，即0<￡<1，如希尔排序。（4）线性阶（O（n））排序：如箱排序和基数排序。

3.3 空间复杂度

空间性能是排序所需辅助空间大小，所有简单排序和堆排序都是O （1）；归并排序和基数排序所需辅助空间最多，为O（n）。

4 结论

排序算法有很多，具体情况中使用哪一种算法很重要。为了选择合适的算法，应顺序考虑以下标准： 执行时间 ，存储空间，编程工作量。数据量较小时，执行时间 和存储空间差别不大，主要考虑编程工作量；当数据量大时， 执行时间为首要。相对来说，简单排序中直接插入排序最好，快速排序最快，当序列为正序时，直接插入排序和冒泡排序都是较好选择。

参考文献

[1] 刘冬莉， 徐立辉. 大学计算机基础教程[M]. 北京：清华大学出版社， 2011.

[2] 严蔚敏， 吴伟民. 数据结构（C语言版）[M] . 北京：清华大学出版社， 2002.

[3] 刘模群. 排序算法时间复杂度研究[J]. 软件导刊， 2012（6）.

作者简介

冯毅宏，女，讲师， 主要从事非线性动力系统图形化和计算机教育研究。