选择类排序法

简单选择排序

基本思想

每趟选择一个关键字最小的记录作为当前要确定的记录。

算法思想

第一趟：选择一个关键字最小的记录，并和第一个记录交换。
第二趟：在剩余的序列中，选择一个关键字最小的记录，并和第二个记录交换。
重复共n-1趟即可完成排序。
第i趟，确定第i个记录
k为最值的下标
j为搜索的下标
在这里插入图片描述

算法分析

最好情况：有序，比较次数n(n-1)/2，移动次数0，时间复杂度为O(n2)。
最坏情况：第一个记录关键字最大，其余记录有序，比较次数n(n-1)/2，移动次数3(n-1)，时间复杂度为O(n2)。
空间复杂度：O(1)。
稳定性：不稳定。

树形选择排序

算法改进要点

简单选择排序：从n个元素中找出关键字最小的记录需要比较n-1次。
从余下的n-1个记录中找出关键字次小的记录是否一定要n-2次比较呢？
改进：把比较过程中的大小关系保存下来。需要空间开销。

算法思想

先将待排序的n个记录的关键字两两比较，取出较小的，然后在选取出来的 n/2 个较小者中，再比较取小者，如此反复，直到选取最小的关键字为止。
为选取次小关键字，将最小关键记录所对应的叶子结点的关键字值置为∞，然后从该叶子结点开始和其兄弟结点的关键字比较，修改从该叶结点到根路径上各结点的值，则根结点的值为次小关键字。
在这里插入图片描述
选出最小关键字27

算法分析

设n个叶子记录，深度为h的满二叉树。
除选择最小关键字外，其余较小关键字的选取均需要比较h-1次,每选一个关键字的比较次数为 log2n 。
比较的时间复杂度为O(nlog2n)。
移动记录的次数不超过比较次数，故总的时间复杂度为O(nlog2n)。
空间复杂度为O(n)。增加了n-1个结点。
稳定性：稳定。当左右孩子相等时，优先左孩子，保证了优先关系不变。

堆排序

算法改进要点

树选排：辅助空间n-1个记录大小。
堆序：辅助空间1个记录大小。

堆的概念

完全二叉树以顺序表方式(数组方式)存储，各结点(即各记录)的关键字满足条件：r[i].key>=r[2i].key并且r[i].key>=r[2i+1].key的完全二叉树被称为大根堆。
即大根堆的结点的关键字大于或等于其左右孩子的关键字。
反之，称为小根堆。
堆排序是完全二叉树顺序结构的应用。
例: 判断下列两个序列是否堆？
{ 98,77,35,62,55,14,35,48 }
{ 14,48,35,62,55,98,35,77 }
在这里插入图片描述

重建堆

解决的问题：当堆顶记录改变时，如何重建堆。
方法：“筛选”法。
辅助空间：一个记录大小的空间。
例如：已知关键字初始序列{ 98,77,35,62,55,
14,35,48 }，其对应的如下图所示。将堆顶记录与堆尾记录交换后，给出剩余记录的调整建堆过程。
顶尾交换，剩余前n-1个记录，确定了第n个记录为关键字最大的记录。
在这里插入图片描述