一、插入排序

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素逐个插入到已排序序列的合适位置，最终得到完整的有序序列。这个过程类似于打扑克牌时将手中的牌按照大小顺序插入已经排好序的牌堆中的过程。

（一）直接插入排序（最基本的插入排序）

（二）折半插入排序

（三）2-路插入排序

（四）希尔排序（又称缩小增量法）

二、交换排序

（一）冒泡排序

从待排序序列的起始位置开始，依次比较相邻的两个元素，如果顺序不符合排序要求（比如要求升序排列，但左边的元素比右边的大），则交换这两个元素的位置，使得较大（或较小）的元素向右（或向左）移动。这样一轮下来，最大（或最小）的元素就会“冒泡”到序列的末尾。然后，再对剩余的未排序部分重复这个过程，直到整个序列有序。

（二）快速排序

通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序

三、选择排序

（一）简单选择排序

每次从未排序的序列中选择最小（或最大）的元素，将其放到已排序序列的末尾（或开头），直到所有元素都被排序完成。

（二）树形选择排序

每个枝结点的关键字都等于其左、右孩子结点中较小的关键字，根结点的关键字就是最小的关键字。

（三）堆排序

首先将待排序序列构建成一个堆（通常是最大堆），然后反复将堆顶元素（最大元素）与堆的最后一个元素交换，并调整堆使其满足堆属性，最终得到一个有序序列。

四、归并排序

它将待排序序列分成子序列，分别对子序列进行递归排序，然后将已排序的子序列合并成一个有序序列。

五、基数排序

基数排序(Radix Sorting) 又称为桶排序或数字排序：按待排序记录的关键字的组成成分(或“位”)进行排序。

六、各种内部排序的比较

（三）稳定性

（1）稳定性：若记录序列中有两个或两个以上关键字相等的记录： Ki=Kj(i≠j，i, j=1, 2, … n)，且在排序前Ri先于Rj(i<j)，排序后的记录序列仍然是Ri先于Rj，称排序方法是稳定的，否则是不稳定的。