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

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

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

1 排序算法分类

1.1 内部排序

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

1.2 外部排序

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

2 常见的排序算法

2.1 插入排序

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

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

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

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