简单选择排序

堆排序

大根堆与小根堆

 把堆看作一个完全二叉树

• 大根堆：父节点大于两个子节点
• 小根堆：父节点小于两个子节点

建立大根堆

• 下沉操作：对于节点n

  • 节点n大于所有的孩子或者节点n没有孩子，就不用操作直接退出，否则进行下面
  • 交换节点n与节点n的大孩子m，然后对m进行同样的操作

• 对于一个无序堆：从最后一个度不为0的节点开始一直递减到根节点，依次进行下沉操作

大根堆的插入

• 上升操作：对节点n

  • 比较节点n与其父亲，如果小于等于其父亲或者节点n已经是根节点了，则不用操作退出。否则进行下面步骤
  • 交换节点n与其父亲m，然后对m进行上升操作

• 首先插入到最后的位置，然后进行上升操作

大根堆的删除

• 删除首个元素：交换根节点与最后一个节点，然后对根节点进行下沉操作