简单选择排序

每次从未排序数组中选择最小的放到有序数组中

• 不稳定算法
• 时间复杂度：O(n²)
• 比较次数数量级与序列初始状态无关，始终是O(n²)

不怎么考

堆排序

• 堆是特殊的完全二叉树

• 大根堆（大顶堆）👇，父节点比子节点大

  • $arr[i]\ge arr[2i+1]andarr[i]\ge arr[2i+2]$$arr[i] \ge arr[2i+1]\ and\ arr[i] \ge arr[2i+2]$

• 小根堆（小顶堆）👇，父节点比子节点小

  • $arr[i]\le arr[2i+1]andarr[i]\le arr[2i+2]$$arr[i] \le arr[2i+1]\ and\ arr[i] \le arr[2i+2]$

• 不稳定算法

• 时间复杂度：O(nlog₂n)

  • 不管最好还是最坏都是O(nlog₂n)

• 基本思想

  • 将无需序列构建成一个堆(完全二叉树)

    • 升序就用大顶堆，降序用小顶堆

  • 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端

    • 下次循环时就不再修改此元素

  • 重新调整结构使其满足堆定义，然后继续交换堆顶元素和末尾元素

  • 反复执行调整和交换步骤，直到整个序列有序

• 取一堆数据中最大(最小)的k个元素时优先使用堆排序

• 堆排序的序列与相当于二叉树的层次序列

• 可以讲堆视作完全二叉树，采用顺序存储方式存放堆

• 插入和删除一个新元素的时间复杂度都为O(log₂n)

• 构造n个记录的初始堆，时间复杂度为O(n)

常考

错题集

1. 

   答案与解析：

   
   答案： D
   解析：
   没看懂
   

2. 

   答案与解析：

   
   答案： D
   解析：
   

3. 

   答案与解析：

   
   答案： B
   解析：
   堆是一棵完全二叉树，小顶堆的最大关键字一定在叶子结点(非叶子结点会有子结点，定义是父结点一定比子结点小)
   完全二叉树的最后一个非叶子结点为$\lfloor n/2\rfloor$$\lfloor n/2 \rfloor$,所以关键字最大纪录的存储范围是$\lfloor n/2\rfloor +1\sim n$$\lfloor n/2 \rfloor + 1 \sim n$

4. 

   答案与解析：

   
   答案： C
   解析：
   删除后最后一位进行补位
   
   先和15比较,符合定义不换位
   再和10比较，不符合定义交换12和10
   再向下判断，与16比较，符合定义不换位
   一共比较3次