本文共 1033 字,大约阅读时间需要 3 分钟。
按照排序过程设计的存储器的不同分为内部排序与外部排序。内部排序完全在内存中进行,适合数据量不太大的数据元素的排序。外部排序需要访问外部存储器,待排序的数据元素非常多,以至于它们必须存储在外部存储器上。
如果对任意一组数据元素序列,使用排序算法排序后,相同关键字之间的前后位置关系在排序前后保持一致,则该排序算法是稳定的。
内排序的过程是一个逐步扩大记录的有序序列长度的过程。基于不同的“扩大”方法,内排序方法可分为插入类、交换类、选择类、归并类。
即在一个已经有序的序列中,插入一个新的记录。这类排序有:直接插入排序、折半插入排序、希尔排序。
该类方法的核心是“交换”,即每趟排序,都是通过一系列的“交换”动作完成的。这类排序有:冒泡排序、快速排序。
该方法的核心是“选择”,即每趟排序都选出一个最小(或最大)的记录,把它和序列中的第一个(或最后一个)记录交换,这样最小(或最大)的记录到位。这类排序有:选择排序、堆排序。
所谓归并,就是将两个或两个以上的有序序列合并成一个新的有序序列。这类排序有:(二路)归并排序。
此类方法较为特别,是基于多关键字排序的思想,把一个逻辑关键字拆分成多个关键字,如一副扑克牌,按照基数排序思想可以先按花色排序,则分成4堆,每堆再按A-K的顺序排序,使得整副扑克牌最终有序。
主要标准是算法的时间复杂度和空间复杂度。常用的排序算法可用谐音的方式来记忆“冒择路兮快归堆”,“冒冒失失的选择道路的话,你就快到坟堆里了”。指的是冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。
各种排序算法的时间复杂度和空间复杂度的性能评价如下:
关于排序算法的选择,可以参考: