常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

​

插入排序

算法步骤：

1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤：

1） 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2） 按增量序列个数k，对序列进行k 趟排序；

3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

选择排序

算法步骤：

1） 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

2） 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3） 重复第二步，直到所有元素均排序完毕。

冒泡排序

算法步骤：

归并排序

算法步骤：

快速排序

算法步骤：

堆排序

基数排序

总 结

关于时间复杂度

（1）平方阶（O（n2））排序

各类简单排序：直接插入、直接选择和冒泡排序；

（2）线性对数阶（O（nlog2n））排序

快速排序、堆排序和归并排序；

（3）O（n1+§）)排序，§是介于0和1之间的常数。

希尔排序

（4）线性阶（O（n））排序

基数排序；此外还有桶、箱排序。

关于空间复杂度

关于稳定性

来源：程序员食堂