1.插入类的排序

在一个已经有序的序列中，插入一个新的关键字，就好比军训排队，已经排好了一个纵队。这时，有人要临时加到这个队里来，于是教官大声喊道：“新来的，迅速找到你的位置，入队！”于是新来的“插入”到这个队伍的合适位置中。这就是“插入”类的排序。属于这类排序的有直接插入排序、折半插入排序、希尔排序。

2.交换类的排序

交换类排序的核心是“交换”，即每一趟排序，都通过一系列的“交换”动作，让一个关键字排到它最终的位置上。还是军训排队的例子，设想军训刚开始，一群学生要排队，教官说：“你比你旁边的高，你俩换一下。怎么换完还比下一个高？继续换……”最后这个同学将被换到最终位置。这就是“交换”类的排序。属于这类排序的有起泡排序（刚才排队的例子）、快速排序。

3.选择类的排序

选择类排序的核心是“选择”，即每一趟排序都选出一个最小（或最大）的关键字，把它和序列中的第一个（或最后一个）关键字交换，这样最小（或最大）的关键字到位。继续军训排队，教官说：“你们都站着别动，我看谁个子最小。”然后教官选出个子最小的同学，说“第一个位置是你的了，你和第一个同学换一下，剩下的同学我继续选。”这就是“选择”类的排序。属于这类排序的有简单选择排序、堆排序。(www.daowen.com)

4.归并类的排序

所谓归并就是将两个或两个以上的有序序列合并成一个新的有序序列，归并类排序就是基于这种思想。我们继续排队，这次教官想了个特别的方法，他说：“你们每个人，先和旁边的人组成一个二人组，二人组内部先排好。”看到大家排好了，继续说：“二人组和旁边的二人组继续组合成一个四人组，每个四人组内部排好，动作快！”这样不停排下去，最后全部学生都归并到了一个组中，同时也就排好序了。这就是“归并”类的排序。这个例子正是二路归并排序，特点是每次都把两个有序序列归并成一个新的有序序列。

5.基数类的排序

基数类的排序是最特别的一类，跟前面的思想完全不同（前面都是要进行“比较”和“移动”这两个操作）。基数类的排序基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字。例如，对一副去掉大小王的52张扑克牌进行基数排序，可以先按花色排序（如按红桃、黑桃、方片和梅花的顺序），这样就分成了4堆，然后每一堆再按照从A到K的顺序，排序使这副牌最终有序。具体排序过程后边会细致讲解。

说明：如果没有特殊说明，本章所有的排序算法都是非递减排序，注意非递减不等于递增，因为有可能出现相同的关键字。