排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。

一、内排序有可以分为以下几类

• (1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
• (2)、选择排序：简单选择排序、堆排序。
• (3)、交换排序：冒泡排序、快速排序。
• (4)、归并排序
• (5)、基数排序

二、时间复杂度分析

二分插入排序跟直接插入排序差不多。忽略系数，最坏情况下也为O(n^2).

三、排序算法的选择

1.数据规模较小

（1）待排序列基本序的情况下，可以选择直接插入排序；

（2）对稳定性不作要求宜用简单选择排序，对稳定性有要求宜用插入或冒泡

2.数据规模不是很大

（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。

（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序

3.数据规模很大

（1）对稳定性有求，则可考虑归并排序。

（2）对稳定性没要求，宜用堆排序

4.序列初始基本有序（正序）

宜用直接插入，冒泡