几种基本的排序算法

排序问题的定义:输入一个线性表,该线性表的元素属于一个偏序集:要求对该线性表的元素做某种重排,使得线性表中除表尾外的每个元素都小于等于(或大于等于)它的后继。排序问题一般分为内排序(internal sorting)和外排序(externalsorting)两类:内排序:待排序的表中记录个数较少,整个排序过程中所有的记录都可以保留在内存中;外排序:待排序的记录个数足够多,以至于他们必须存储在磁带、磁盘上组成外部文什,排序过程中需要多次访问外存。从算法的角度来看,外排序可以看作是内排序的扩展和综合,所以本文着重介绍几种典型的内排序算法。