排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

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

各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：

思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置，直到全部插入排序完为止。  关键问题：在前面已经排好序的序列中找到合适的插入位置。  方法：

插入排序示意图

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。  关键问题：在剩余的待排序记录序列中找到最小关键码记录。  方法：

基本思想

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

 基本思想

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆是具有以下性质的完全二叉树：

通过图可以比较直观的看出大根堆和小根堆的特点，需要注意的是：这种结构是对父节点-左/右孩子节点之间做的约束，而对左-右孩子节点之间并没有什么要求。

另外，因为堆的结构是完全二叉树，所以可以用数组来存储，并通过节点下标的规律快速进行索引。

下面是上图大根堆与小根堆对应的数组：

假设现在待排序数据存在array[count]中，其初始状态如下：

对应的完全二叉树为：

堆排序的过程如下：

（1）初始化堆；

因为堆是对父节点-左/右孩子节点之间的约束，所以从最后一个非叶子节点开始调整。

注意每次交换后，都要对下一层的子堆进行递归调整，因为交换后有可能破坏已调整子堆的结构。

（2）进行调整后，堆顶元素（array[0]）为最大值，将最大值与堆尾部元素（array[count-1]）交换，并将count值减去1，则此时得到新的无序数组array[count]，此时的堆被破坏；

对应到数组元素为：

（黄色标记为已排序部分）

（3）调整堆：与建堆过程类似，堆顶元素被一个比较小的值代替，所以从堆顶元素开始调整，在堆顶、堆顶的左孩子、堆顶的右孩子中找出最大的与堆顶进行交换，被交换的元素再次与他下一层的左右孩子进行比较（递归）调整。

（4）重复（2）。

下面把整个过程画完：

此时，大概的一个手工过程就懂了，注意的是：初始化堆是基础，时从下向上调整。交换后调整堆时因为有了建堆的基础，每次调整的都是二叉树的一支子树，是从上往下。

输出结果：