内部排序(四):选择排序 Selection Sorting (简单选择排序、堆排序)
程序员文章站
2022-06-04 09:52:34
...
作为数据结构的课程笔记,以便查阅。如有出错的地方,还请多多指正!
注:C++忘得太厉害了。。算法先用C实现,等之后复习了再改成C++
目录
简单选择排序 Simple Selection Sort
排序过程
思路:
- 首先通过
n-1
次关键字比较,从n
个记录中找出关键字最小的记录,将它与第一个记录交换 - 再通过
n-2
次比较,从剩余的n-1
个记录中找出关键字次小的记录,将它与第二个记录交换 - 重复上述操作,共进行
n-1
趟排序后,排序结束
算法实现
void Simple_selection_sort(SqList_t* list)
{
for (int i = 1; i < list->len; ++i)
{
int min = i;
for (int j = i + 1; j <= list->len; ++j)
{
if (list->rec[min].key > list->rec[j].key)
{
min = j;
}
}
if (min != i)
{
list->rec[0] = list->rec[i];
list->rec[i] = list->rec[min];
list->rec[min] = list->rec[0];
}
}
}
算法评价
T(n)
选择排序需执行趟。第趟排序需要比较次
- 比较次数:
若待排记录为从小到大排列(正序)
- 移动次数:
若待排记录为从大到小排列
- 移动次数:
S(n)
是否稳定
- 不稳定
堆排序 Heap Sort
堆
概念
-
堆采用完全二叉树结构
-
使用顺序存储。即按层序存储,所用数组起始单元为1,则结点的父结点为,左、右孩子为,
-
最大堆 / 大顶堆 (max heap):任一结点的值 其子结点的值
因此最大堆中根结点元素最大 -
最小堆 / 小顶堆 (min heap):任一结点的值 其子结点的值
因此最小堆中根结点元素最小
排序过程
思路:
- 初建堆:将无序序列建成一个堆,则堆顶是关键字最小(或最大) 的记录
- 调整堆:输出堆顶记录后,将剩余的记录重新调整成一个新堆,则可得到剩余记录中的最小值(或最大值)
- 重复执行上一步 ,直到得到一个有序序列
调整堆:筛选
以最小堆为例:
- 将堆顶记录(根)与堆中最后一个记录交换位置
- 然后将根结点值与其左、右孩子进行比较,并与其中小的进行交换
- 重复上述操作,直至叶子结点,将得到新的堆,这个从堆顶至叶子的调整过程称为“筛选”
可以看出,最小堆适合于降序排序,而最大堆适合于升序排序
初建堆
从无序序列的第个元素(即此无序序列对应的完全二叉树的最后一个非叶子结点)起,至第一个元素止,进行反复筛选
算法实现
- 要进行升序排序,因此实现最大堆
void Heap_adjust(SqList_t* list, int root, int len)
{
int min_child;
list->rec[0] = list->rec[root];
while (root * 2 <= len)
{
min_child = root * 2;
if (min_child + 1 <= len
&& list->rec[min_child + 1].key > list->rec[min_child].key)
{
++min_child;
}
if (list->rec[min_child].key > list->rec[0].key)
{
list->rec[root] = list->rec[min_child];
root = min_child;
}
else {
break;
}
}
list->rec[root] = list->rec[0];
}
void Heap_sort(SqList_t* list)
{
//初建堆
for (int i = list->len / 2; i >= 1; --i)
{
Heap_adjust(list, i, list->len);
}
//输出 n-1 次,调整堆 n-2 次
for (int i = 0; i < list->len - 1; ++i)
{
if(i > 0)
{
Heap_adjust(list, 1, list->len - i);
}
list->rec[0] = list->rec[1];
list->rec[1] = list->rec[list->len - i];
list->rec[list->len - i] = list->rec[0];
}
}
算法评价
T(n)
堆排序的运行时间主要耗费在:
-
初建堆: 次筛选
对深度为的堆进行筛选时,最多进行次关键字比较。由于第层上的结点数最多为,以它们为根的二叉树深度为。
因此,初建堆时最大的比较次数为:
-
调整成新堆: 次筛选
因为个结点的完全二叉树最大深度为,因此比较次数最多为:
综上所述,堆排序即使在最坏的情况下,时间复杂度依然为
S(n)
是否稳定
- 不稳定
总结
- 记录数较少的序列,堆排序的优越性并不明显,但对大量的记录来说堆排序是很有效的
推荐阅读
-
PHP排序算法之简单选择排序(Simple Selection Sort)实例分析
-
PHP简单选择排序(Simple Selection Sort)算法学习
-
PHP简单选择排序(Simple Selection Sort)算法学习
-
PHP排序算法之简单选择排序(Simple Selection Sort)实例分析
-
c++实现简单选择排序和堆排序
-
内部排序(四):选择排序 Selection Sorting (简单选择排序、堆排序)
-
php数据结构 算法(PHP描述) 简单选择排序 simple selection sort_php技巧
-
PHP排序算法之简单选择排序(Simple Selection Sort)
-
PHP简单选择排序(Simple Selection Sort)算法学习
-
php数据结构 算法(PHP描述) 简单选择排序 simple selection sort