数据结构 第3页

2023-03-25阅读(265)

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

2023-03-25阅读(170)

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

2023-03-25阅读(200)

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

2023-03-25阅读(238)

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

2023-03-24阅读(262)

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

2023-03-24阅读(232)

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

2023-03-24阅读(213)

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

2023-03-24阅读(210)

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

2023-03-24阅读(322)

一、概念及其介绍 归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，...

2023-03-23阅读(262)

一、概念及其介绍 希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。 希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。 它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算...