内部排序

1、直接插入排序

从后面的序列中先把第一个数字提出来，然后拿第二个数字和它比较，如果大则放在右面，如果小则排在左面，排好之后，再把第三个数字排好的数字从右往左依次比较，找到适合的位置插入平均时间复杂度O(n²)，空间复杂度O(1)。

2、折半插入排序

注意！折半插入是把新的元素插入到一个已经有序的序列中思路类似于二分查找，每次取中间的作比较，直到最后找到合适的位置插入就行了。

3、希尔排序

首先先了解排序算法的稳定性：如果队列中存在两个相等的数字排序过程中这两个数字的先后顺序如果不会发生变化就叫做稳定的排序反之叫做不稳定。希尔排序向下取整

个人理解：希尔排序就是直接插入排序的2.0版本，希尔排序本身就属于插入排序，如果直接用直接插入排序可能时间复杂度太高，而经过希尔排序前面的这一系列分组排序，再分组再排。这样处理的话，可以减少工作量，从而减少复杂度。希尔排序不稳定。

4、冒泡排序

5、快速排序

因为用到了递归，所以平均时间复杂度为O(nlog₂n)，空间复杂度O(log₂n)从左往右扫描，同时从右往左扫描。以49 38 65 97 76 13 27为例子

把第一个数字作为基准然后从右往左开始找第一个比49小的数，然后把这个数移动到i的位置所以j的位置现在是空的

接下来让i往右移动，找到第一个比49大的，然后把这个数移动到j的位置，这个时候i就变成空的

接下来重复上面的操作开始移动j,最后i和j会汇合，此时ij上面的块是空的，然后把49放进去，这样左边都比49小，右边都比49大。

接下来就把49左边和右边看成两个整体，重复上面操作，还是各自以第一个为数字为基准。最终得到有序序列。

6、简单选择排序

就是扫描无序的序列，每次找出来最小的哪一个放到最前面，然后再从后面找出最小的排在前面那个元素后面。直到扫描了全部的元素。时间复杂度为O(n²)

7、堆排序

完全二叉树有个特性：左边子节点位置=当前父节点的两倍+1，右边子节点位置=当前父节点的两倍+2

堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法

适合类型的堆来进行排序：升序—使用大顶堆降序—使用小顶堆

个人理解：

从整个树的最右下面的叶子结点开始，看它的父结点和左右两个子结点的大小，那个小则与父结点调换位置，再按照逆层次遍历的顺序继续往前找...最后调整到根结点就是最小元素，然后把这个最小的元素，与最右下面的叶子结点调换位置，这样就排好一个元素了，初始堆建好之后，最有下面的叶子结点不是已经调换到根结点的位置了吗，之后再调整，只需要从根结点往下调整就行了。

堆不是平衡二叉树。
首先，我们应该有这样的一个约定：二叉平衡树肯定是一颗二叉排序树。
因为只有这样，二叉平衡树才有存在的意义。我们引入二叉平衡树，就是为了解决二叉排序树的查找效率问题。
这样的话，堆肯定就不是一颗平衡二叉树了，二叉排序树：或是一颗空树，或者是结点的左子树上的结点关键字都比该结点关键字值小
，该结点的右子树上的结点关键字之都比该结点的关键字值大，并且是递归定义的。
堆：对于一个数组中的关键字，如果按照完全二叉树的结点来造树，则完全二叉树中的非终端结点关键字值不大于（不小于）其左右孩子的值。

所以综上所述可知，堆不是一颗二叉平衡树。