4.选择排序

选择排序的基本思想是：每一趟（如第 $i$ 趟）在后面 $n-i+1 ( i=1,2, \cdots, n-1)$ 个待排序元 素中选取关键字最小的元素, 作为有序子序列的第 $i$ 个元素, 直到第 $n-1$ 趟做完, 待排序元素只 剩下 1 个, 就不用再选了。

简单选择排序

每一趟排序可以确定一个元素的最终位置,这样经过 $n-1$趟排序就可使得整个排序表有序。

• 空间效率$O(1)$
• 元素间比较的次数与序列的初始状态无关,始终是$n(n-1)/2$次,因此时间复杂度始终是$O(n^2)$
• 元素移动的操作次数很少,不会超过 $3(n-1)$次,最好的情况是移动$0$次,此时对应的表已经有序
• 不稳定

堆排序

8.4.2_1堆排序

---

00:01

【课件】8.4.2_1堆排序

---

堆的定义如下, $n$ 个关键字序列 $L[1...n]$称为堆, 当且仅当该序列满足:

1. $L(i)>=L(2 i)$ 且 $L(i)>=L(2 i+1)$ 或
2. $\mathrm{L}(i)<=\mathrm{L}(2 i)$ 且 $\mathrm{L}(i)<=L(2 i+1) (1 \leqslant i \leqslant\lfloor n / 2\rfloor)$
   可以将堆视为一棵完全二叉树, 满足条件(1)的堆称为大根堆 (大顶堆), 大根堆的最大元素 存放在根结点, 且其任意一个非根结点的值小于或等于其双亲结点值。满足条件(2)的堆称为小根 堆 (小顶堆), 小根堆的定义刚好相反, 根结点是最小元素。图所示为一个大根堆。

image.png

在建含$n$个元素的堆时，关键字的比较总次数不超过$4n$,时间复杂度为$O(n)$，这说明可以在线性时间内将一个无序数组建成一个堆。

在向有 $n$ 个元素的堆中插入一个新元素时, 需要调用一个向上调整的算法,调整的时间与树高有关，为$O(h)$。 比较次数最多等 于树的高度减 1 , 由于树的高度为 $\left\lfloor\log _{2} n\right\rfloor+1$, 所以堆的向上调整算法的比较次数最多等于 $\left\lfloor\log _{2} n\right\rfloor$

即调整堆和建初始堆的时间复杂度是不一样的,

提示

堆排序适合关键字较多的情况。例如,在1亿个数中选出前100个最大值?首先使用一个大小为 100 的数组,读入前100个数,建立小项堆,而后依次读入余下的数,若小于堆项则舍弃, 否则用该数取代堆顶并重新调整堆,待数据读取完毕,堆中100 个数即为所求。

• 空间复杂度$O(1)$
• 时间效率: 建堆时间为 $O(n)$, 之后有 $n-1$ 次向下调整操作, 每次调整的时间复杂度为 $O(h)$, 故在最好、最坏和平均情况下, 堆排序的时间复杂度为 $O\left(n \log _{2} n\right)$ 。
• 不稳定

注意

建堆时，直接按树的层序遍历建，然后再调整，后最下一层非叶子结点开始调整