快速排序，对冒泡排序的一种改进

  最广泛的排序算法，实现简单，适用于各种不同的输入数据，一般应用中，比其他排序快的多。

特点：1.原地排序（只需要一个很小的辅助栈）2.内循环比较小

 也是一种分治的排序算法。将一个数组分成两个数组，将两部分独立排序。

  快速排序和归并排序是互补的，归并排序，两个排好的整合到一起。而快速排序，两个子数组都有序，则整个数组自然有序。

  第一个，递归调用，发生在处理数组之前。  第二种，则发生在处理之后。

一趟排序分为两部分，一部分的数据，都比另一部分的小。然后对两部分分别快速排序。

优先队列

  处理有序的元素。该数据类型支持，删除最大元素和插入元素。叫优先队列。

  优先队列的使用  和 队列（删除最老元素） 和栈（删除最新元素）类似。

  通过插入一列元素，然后一个个删掉最小元素，可以用优先队列实现堆排序算法。

堆的定义

堆，是数据结构中的堆，不是内存模型中的堆。对可以被看成一棵树。

满足：①堆中任意节点的值，总是不大于（不小于）其子节点的值 ②堆总是一颗完全树

二叉堆，能够很好的实现优先队列的基本操作。它是完全二叉树或者近似完全二叉树（最大堆和最小堆）。

二叉堆数组中，每个元素都保证，大于等于另外两个特定位置的元素。

当一颗二叉树的每个结点，都大于等于它的两个叶子结点，它被称为堆有序。

二叉堆，一般通过数组实现。 索引为树的表示

如果根节点，为0也就是a[0]， 那么左结点为(2*i+1) 右结点为(2*i+2) 结点的父节点(i-1)/2

如果我们在上图的最大堆添加，85：

  

如果我们在上图的最大堆中删除一个：90

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

基本思想：构造最大堆或者最小堆，然后根据每次删除最大元素 或者 最小元素。来进行一次插入排序。

一般升序用 最大堆，降序使用最小堆

每次将最大根节点，取出，然后将剩下的节点组成最大堆。然后再取出根节点。

属于一种选择排序。