服务端 第12页

2023-03-25阅读(607)

一、概念及其介绍 索引堆是对堆这个数据结构的优化。 索引堆使用了一个新的 int 类型的数组，用于存放索引信息。 相较于堆，优点如下： 优化了交换元素的消耗。 加入的数据位置固定，方便寻找。 二、适用说明 如果堆中存储的元素较大，那么进行交...

2023-03-25阅读(306)

上一节的堆排序，我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节，我们进行优化，使用原地堆排序。 对于一个最大堆，首先将开始位置数据和数组末尾数值进行交换，那么数组末尾就是最大元素，然后再对W元素进行 shift down 操作，重新...

2023-03-25阅读(564)

一、概念及其介绍 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。 堆是一个近似 完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 二、适用说明 我们之前构造堆的过程是一个个...

2023-03-25阅读(327)

本小节将介绍如何从一个最大堆中取出一个元素，称为 shift down，只能取出最大优先级的元素，也就是根节点，把原来的 62 取出后，下面介绍如何填补这个最大堆。 第一步，我们将数组最后一位数组放到根节点，此时不满足最大堆的定义。 调整的...

2023-03-25阅读(334)

本小节介绍如何向一个最大堆中添加元素，称为 shift up。 假设我们对下面的最大堆新加入一个元素52，放在数组的最后一位，52大于父节点16，此时不满足堆的定义，需要进行调整。 首先交换索引为 5 和 11 数组中数值的位置，...

2023-03-25阅读(457)

一、概念及其介绍 堆(Heap)是计算机科学中一类特殊的数据结构的统称。 堆通常是一个可以被看做一棵完全二叉树的数组对象。 堆满足下列性质： 堆中某个节点的值总是不大于或不小于其父节点的值。 堆总是一棵完全二叉树。 二、适用说明 堆是利用完...

2023-03-24阅读(401)

本小节对本教程的排序算法做一个总结。 （1）归并排序和快速排序都使用了分治算法。 顾名思义，就是将原问题分割查能同等结构的子问题，之后将子问题逐一解决后，原问题也就得到了解决。 （2）逆序对的定义 如果存在正整数 i, j 使得 1 ≤ i...

2023-03-24阅读(380)

一、概念及其介绍 三路快速排序是双路快速排序的进一步改进版本，三路排序算法把排序的数据分为三部分，分别为小于 v，等于 v，大于 v，v 为标定值，这样三部分的数据中，等于 v 的数据在下次递归中不再需要排序，小于 v 和大于 v 的数据也...

2023-03-24阅读(340)

一、概念及其介绍 双路快速排序算法是随机化快速排序的改进版本，partition 过程使用两个索引值（i、j）用来遍历数组，将 <v 的元素放在索引i所指向位置的左边，而将 >v 的元素放...

2023-03-24阅读(427)

一、概念及其介绍 快速排序由 C. A. R. Hoare 在 1960 年提出。 随机化快速排序基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进...