以int型数据为例，且0号下标数组用来做为交换辅助空间，数据从1号下标开始存储

基本思想：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到全部待排序记录全部插入为止。

排序过程：

1、将待排序数组arr[1…n]看作两个集合，arr[1]为有序集合中元素，arr[2…n]为无序集合中元素，a[0]用来临时存放当前待排序记录

2、外层循环每次从无序集合中选择一个待插入元素(n-1次)，每次使用顺序查找法，内层循环查找arr[i]在有序集合中的位置（将有序集合中大于待插入元素的记录后移一位）

时间复杂度：

​ 堆排序平均性能接近于最坏性能，时间复杂度为O(nlog2 n)

空间复杂度：

​ 仅用arr[0]作为交换辅助空间，空间复杂度为O(1)

算法特点：

​ 1、不稳定排序

​ 2、只能用于顺序结构，不能用于链式结构

​ 3、初始建堆所需要的比较次数比较多，记录较少时不宜采用，堆排序在最坏情况下的时间复杂度为O(nlog2 n)，相对于快速排序最坏情况下的O(n^2)而言是个优点，当记录较多时较为高效。

基本思想：假设初始序列含有n个记录，则可看成时n个有序的子序列，每个子序列的长度为1，然后两两并归，得到n/2个长度为2或1的有序子序列；如此重复，直至得到一个长度为n的有序序列为止。