文心一言 VS 讯飞星火 VS chatgpt (171)-- 算法导论13.2 4题

2024-01-04 11:28

本文主要是介绍文心一言 VS 讯飞星火 VS chatgpt (171)-- 算法导论13.2 4题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

四、用go语言,证明:任何一棵含n个结点的二叉搜索树可以通过 O(n)次旋转,转变为其他任何一棵含n个结点的二叉搜索树。(提示:先证明至多n-1次右旋足以将树转变为一条右侧伸展的链。)

文心一言:

这是一个有趣的问题,我们可以使用递归和数学归纳法来证明这个结论。

首先,让我们定义一个函数rotate(node),该函数将给定的节点node作为根的子树向右旋转。这个函数将递归地处理左右子树。

假设我们有一个节点root,并且它的左子树为空。我们可以使用rotate(root.right)来将右子树旋转,这样root就变成了右子树的根,右子树的原根变成了root的左子树。

现在我们需要证明至多n-1次右旋可以使得一棵二叉搜索树变为一条右侧伸展的链。

首先,考虑一个二叉搜索树中的任意节点。这个节点要么是叶节点(没有子节点),要么有两个子节点。如果一个节点有右子节点,那么它的右子节点的左子节点(如果存在)一定比该节点小。因此,我们可以找到一条从根到叶节点的路径,沿着这条路径的节点都是按照升序排列的。这条路径上的节点就是我们要伸展的链。

我们可以通过不断地将这条路径上的节点旋转到右侧,来使得整棵树变为一条伸展的链。每旋转一次,我们都会去掉一个节点,因此最多需要旋转n-1次。

然后,我们可以通过不断地将这条伸展的链旋转到左侧,来得到任意其他的二叉搜索树。每旋转一次,我们都会添加一个节点,因此最多需要旋转n-1次。

因此,我们证明了任何一棵含n个结点的二叉搜索树可以通过 O(n)次旋转,转变为其他任何一棵含n个结点的二叉搜索树。

在这里插入图片描述

讯飞星火:

首先,我们需要证明至多n-1次右旋足以将树转变为一条右侧伸展的链。

假设我们有一个二叉搜索树T,其中每个节点的值都大于其左子树中的所有节点的值,且小于其右子树中的所有节点的值。现在,我们将T进行n-1次右旋,得到一个新的二叉搜索树T’。

为了证明T’是一个右侧伸展的链,我们需要证明以下两个条件:

  1. T’的根节点的值等于T的最大值。
  2. T’的左子树是T的左子树经过n-1次右旋得到的。

根据这两个条件,我们可以得出以下结论:

  1. 对于任意一个节点x,如果x在T中的位置为i,那么x在T’中的位置也为i。
  2. 对于任意一个节点x,如果x在T中的位置为i,那么x在T’中的位置为i+1。
  3. 对于任意一个节点x,如果x在T中的位置为i,那么x在T’中的位置为i-1。

由于T’的根节点的值等于T的最大值,所以T’的根节点在T中的位置为n-1。因此,我们可以得出结论:

  1. T’的根节点在T中的位置为n-1。
  2. T’的左子树在T中的位置为1到n-2。
  3. T’的右子树在T中的位置为n。

接下来,我们需要证明T’的右子树是T的右子树经过n-1次右旋得到的。

假设我们已经证明了T’的左子树是T的左子树经过n-1次右旋得到的,那么我们可以通过以下步骤证明T’的右子树也是T的右子树经过n-1次右旋得到的:

  1. 将T的右子树进行n-1次右旋,得到一个新的二叉搜索树T’'。
  2. 将T’'的左子树作为T’的右子树。

这样,我们就得到了一个新的二叉搜索树T’',它满足以下条件:

  1. T’'的根节点的值等于T的最小值。
  2. T’'的左子树是T的左子树经过n-1次右旋得到的。
  3. T’'的右子树是T的右子树经过n-1次右旋得到的。

综上所述,我们证明了任何一棵含n个结点的二叉搜索树可以通过O(n)次旋转,转变为其他任何一棵含n个结点的二叉搜索树。

在这里插入图片描述

在这里插入图片描述

360智脑:

首先,我们需要明确旋转的概念。在AVL树中,旋转操作是用来重新平衡树的某个部分的。当向AVL树中插入一个节点后,如果任何平衡因子变成了+/-2,就必须从这个节点开始往下重新平衡这颗树,这个重新平衡的过程就称为旋转。旋转操作可以分为4种:LL(左左旋转)、LR(左右旋转)、RL(右左旋转)和RR(右右旋转)。

接下来,我们证明至多n-1次右旋足以将树转变为一条右侧伸展的链。我们可以通过递归的方式来进行证明。假设我们已经将一棵含有k个节点的二叉搜索树通过至多k-1次右旋转变为一条右侧伸展的链,现在我们要将一棵含有k+1个节点的二叉搜索树通过至多k次右旋转变为一条右侧伸展的链。

对于含有k+1个节点的二叉搜索树,我们可以找到它的最右边的节点,然后将该节点作为新的根节点,将原来的根节点作为其左子节点,这样就形成了一棵含有k个节点的二叉搜索树。由于我们已经假设了至多k-1次右旋可以将含有k个节点的二叉搜索树转变为一条右侧伸展的链,所以我们可以将这棵含有k个节点的二叉搜索树通过至多k-1次右旋转变为一条右侧伸展的链。

接下来,我们需要将原来的根节点作为新根节点的左子节点。由于原来的根节点比新根节点小,所以我们可以将原来的根节点插入到新根节点的左子树中。由于插入操作不会影响到右旋操作的结果,所以我们可以继续使用至多k-1次右旋来将含有k+1个节点的二叉搜索树转变为一条右侧伸展的链。

综上所述,我们证明了至多n-1次右旋足以将一棵含有n个节点的二叉搜索树转变为一条右侧伸展的链。

最后,我们需要证明任何一棵含有n个节点的二叉搜索树可以通过O(n)次旋转转变为其他任何一棵含有n个节点的二叉搜索树。由于旋转操作可以分为4种,每种旋转操作都会改变树的结构,所以我们可以通过适当的旋转操作来改变树的结构。在最坏的情况下,我们需要进行n次旋转操作来将一棵含有n个节点的二叉搜索树转变为其他任何一棵含有n个节点的二叉搜索树。因此,我们可以使用O(n)次旋转来将任何一棵含有n个节点的二叉搜索树转变为其他任何一棵含有n个节点的二叉搜索树。

在这里插入图片描述

智谱清言:

在Go语言中证明这个结论可以通过编写一个函数来模拟旋转操作,并展示如何通过至多n-1次旋转将二叉搜索树(BST)转换为右侧伸展的链表。这里我们首先定义一个二叉树的节点结构,然后实现旋转和转换函数。

首先,定义一个二叉树节点的结构体:

type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}

接着,我们定义一个函数来执行旋转操作。在二叉搜索树中,旋转操作通常是指左旋或右旋,这里为了简化问题,我们只考虑右旋:

func rightRotate(y *TreeNode) {x := y.LeftT2 := x.Right// Perform rotationx.Right = yy.Left = T2// Update parentif T2 != nil {T2.Parent = y}
}

为了便于讨论,这里我们假设每个节点都有一个指向父节点的指针(这在实际应用中并不常见,因为BST通常不存储父节点信息,但为了讨论方便,我们这里添加了父节点指针)。所以我们需要修改TreeNode结构,添加一个Parent *TreeNode字段。

现在我们来证明至多n-1次右旋足以将树转变为一条右侧伸展的链。为此,我们实现一个函数,它接受一个BST的根节点,并返回一个经过旋转的、右侧伸展的链表的根节点:

func convertBST(root *TreeNode) *TreeNode {var current *TreeNode = rootvar prev *TreeNode = nil// Traverse to the farthest left node, which will become the head of the listfor current != nil {prev = currentcurrent = current.Left}// Start from the farthest left node and perform rotationsfor current != nil {// Save the next nodenext := current.Right// Rotate rightrightRotate(current)// Move to the next nodecurrent = next}// Find the new root of the rotated tree (it will be the leftmost node)var newRoot *TreeNode = nilfor root != nil {if root.Left == nil {newRoot = rootbreak}root = root.Left}return newRoot
}

这个函数首先找到最左侧的节点,然后从这个节点开始,对其每一个节点执行右旋操作。每次旋转都会将当前节点提升到其父节点的位置,并使其原来的右子节点成为新的左子节点。通过这种方式,我们可以将任何一棵含有n个节点的BST转换为一条右侧伸展的链表,且整个过程需要至多n-1次旋转。
最后,需要注意的是,虽然我们通过这种方法可以证明BST可以通过至多n-1次旋转转换为任何其他形态的BST,但这并不意味着旋转操作可以在O(n)时间内完成,因为每次旋转都需要遍历树找到特定的节点。实际上的时间复杂度可能会高于O(n),这取决于如何实现查找和更新节点的操作。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

通义千问:

在二叉搜索树(BST)中,通过旋转操作可以将任意一棵BST转换成另一棵具有相同元素的不同形态的BST。对于含n个节点的二叉搜索树,确实可以通过一系列旋转操作将其转变为任何其他合法的含n个节点的二叉搜索树,并且这个转换过程中所需的旋转次数至多为O(n)。

首先,我们需要了解二叉搜索树中的旋转操作,主要有两种:

  1. 右旋(Right Rotation / RR):对于一个节点p和其左孩子l,右旋操作会使得l成为新的根节点,p成为l的右孩子,同时保持原有的搜索树性质不变。
     p            l/ \   ->    / \a   l      p   r/ \         / \b   r       c   d
  1. 左旋(Left Rotation / LR):与右旋相反,对于一个节点p和其右孩子r,左旋操作会使得r成为新的根节点,p成为r的左孩子。

要将任意BST转为右侧伸展链(所有节点的左子树为空),可以通过不断对每个节点进行右旋操作来实现。由于每次右旋都会至少减少一个非空左子树节点(除了最底层叶子节点外),因此至多需要对n-1个非叶子节点进行右旋,即可得到一条右侧伸展的链状结构。

然后,从右侧伸展链到任何其他形态的BST,可以通过反向旋转(即适当使用左旋和右旋组合)来实现。这个过程可能需要遍历整个链,对于每个节点都有可能进行旋转操作,但考虑到最坏情况下,每层节点都完全不平衡,即形成了一种高度为n的单链状结构,此时为了重新平衡整棵树,确实最多需要进行n次旋转操作。

总结来说,尽管实际转换过程中所需的旋转次数可能会远小于n,但在理论上证明至多可通过O(n)次旋转完成任意两棵大小为n的二叉搜索树之间的转换。

在这里插入图片描述

天工:

首先,我们可以通过一个例子来直观地理解这个问题。假设我们有以下的二叉搜索树:

          10/   \3      7/     /   \2     4    6/   /     \1   5       8

我们的目标是通过旋转将其转变为以下的形式:

          10/   \7     6/     /   \4     3    8/   /     \2   5       8

我们可以看到,我们需要进行两次旋转。首先,我们将根节点的右子树进行右旋转,得到:

          10/   \7     6/     /   \4     3    8/   /     \2   5       8

然后,我们将根节点的左子树进行右旋转,得到:

          10/   \7     6/     /   \4     3    8/   /     \2   5       8

现在,我们可以看到,我们成功地通过两次旋转将原来的二叉搜索树转变为了目标的二叉搜索树。

现在,我们来证明这个结论。对于任何一个含有n个节点的二叉搜索树,我们可以将其看作是一个有n个节点的序列。我们的目标是通过旋转将这个序列转变为另一个有n个节点的序列。我们可以看到,如果一个二叉搜索树的根节点的左子树的深度比右子树的深度大1,那么我们只需要进行一次右旋转就可以将其转变为另一个有n个节点的序列。因此,我们只需要进行n-1次右旋转就可以将任何一棵含有n个节点的二叉搜索树转变为另一个含有n个节点的二叉搜索树。

现在,我们来证明任何一棵含有n个节点的二叉搜索树可以通过O(n)次旋转转变为其他任何一棵含有n个节点的二叉搜索树。首先,我们可以通过上述的方法进行n-1次右旋转将其转变为一个右侧伸展的链。然后,我们只需要进行一次左旋转就可以将这个链转变为一个二叉搜索树。因此,我们只需要进行n次旋转就可以将任何一棵含有n个节点的二叉搜索树转变为其他任何一棵含有n个节点的二叉搜索树。因此,我们的结论是正确的。

在这里插入图片描述

在这里插入图片描述

灵小智:

在证明任意一棵含n个节点的二叉搜索树可以通过O(n)次旋转转变为其他任意一棵含n个节点的二叉搜索树之前,我们先来证明一个辅助性质。

性质:任意一棵含n个节点的二叉搜索树,经过至多n-1次右旋操作,可以变为一条右侧伸展的链。

证明:
设根节点为A,左子树为B,右子树为C。由于是二叉搜索树,B中的所有节点都小于A,C中的所有节点都大于A。

首先,考虑右旋操作将树的形态进行改变。当右旋以A为基准进行时,C成为新的根节点,A成为新根节点的左子树,而B仍然是A的右子树,且大于A,小于C。

重复执行右旋操作,将新的根节点作为基准,每次旋转的结果是将根节点的右子树变为根节点的左子树,而原来的左子树成为新的根节点的右子树。这样不断地进行右旋,根节点的右子树不断增加,而根节点的左子树为空。

因为树 ** 有n个节点,所以至多经过n-1次右旋操作,树就会变为一条右侧伸展的链,其中根节点为最大的节点,且其他节点按照大小顺序连接。

接下来,我们使用上述性质证明任意一棵含n个节点的二叉搜索树可以通过O(n)次旋转转变为其他任意一棵含n个节点的二叉搜索树。

证明:
假设我们有两棵二叉搜索树T1和T2,它们都含有n个节点。

根据上述性质,我们可以将T1通过至多n-1次右旋操作转变为一条右侧伸展的链。此时,T1的根节点为最大的节点。

同样地,我们可以将T2通过至多n-1次右旋操作转变为一条右侧伸展的链。此时,T2的根节点为最大的节点。

由于T1和T2都是右侧伸展的链,并且根节点都是最大的节点,因此它们的结构完全相同。

接下来,我们只需将T1的根节点换成T2的根节点,并进行一次旋转操作,即可将T1转变为T2。

由此可见,通过O(n)次旋转操作,我们可以将任意一棵含n个节点的二叉搜索树转变为其他任意一棵含n个节点的二叉搜索树。

这样我们证明了任意一棵含n个节点的二叉搜索树可以通过O(n)次旋转,转变为其他任意一棵含n个节点的二叉搜索树。

在这里插入图片描述

在这里插入图片描述

chatgpt:

要证明任何一棵含有n个节点的二叉搜索树可以通过O(n)次旋转,转变为其他任何一棵含有n个结点的二叉搜索树,我们可以按照如下步骤进行证明:

  1. 首先证明至多n-1次右旋足以将树转变为一条右侧伸展的链。假设我们有一个含有n个结点的二叉搜索树T,通过对T进行至多n-1次右旋操作,我们可以将其转变为右侧伸展的链L。这是因为每次右旋操作都会将当前节点提升为根节点,并且左子树会被移动到该节点的右子树上。由于二叉搜索树的性质保证了右子树中所有节点的值大于该节点,所以经过至多n-1次右旋后,最终得到的链L满足所有结点值从左到右递增。

  2. 接下来我们需要证明对于任意两条右侧伸展的链A和B(长度均为n),它们可以相互转换。由于两条链都是从小到大排序的序列,所以只需将A中第i个节点与B中第i个节点进行交换即可完成转换(其中i取值范围为1到n)。而交换两个结点等效于在二叉搜索树中交换两个结点的位置,因此可以通过O(n)次旋转来实现。

综上所述,通过至多n-1次右旋将任意一棵含有n个结点的二叉搜索树转变为右侧伸展的链,然后通过交换节点来相互转换链,最终可以得到任何一棵含有n个结点的二叉搜索树。而每次旋转操作都是常数时间复杂度O(1),所以整个过程最多需要O(n)次旋转。

在这里插入图片描述

kimi:

在二叉搜索树(BST)中,旋转操作通常用于在插入或删除操作后保持树的平衡。要证明任何一棵含有 n 个节点的二叉搜索树可以通过 O(n) 次旋转转变为其他任何一棵含有 n 个节点的二叉搜索树,我们可以分解这个问题为几个步骤。

首先,我们证明至多 n-1 次右旋可以将树转变为一条右侧伸展的链。然后,我们可以通过左旋操作将这个链调整为任何其他形状的二叉搜索树。

  1. 将树转变为右侧伸展的链:

    对于树中的每个非叶节点,我们可以执行右旋操作。右旋操作会将节点的左子树提升为新的父节点,而原节点成为新父节点的右子节点。通过这种方式,我们可以将树的结构逐渐转变为一条右侧伸展的链。由于树中有 n-1 个非叶节点,因此最多需要 n-1 次右旋操作。

  2. 通过左旋操作调整链的形状:

    一旦我们有了右侧伸展的链,我们可以通过左旋操作来调整链的形状,以构建任何其他形状的二叉搜索树。左旋操作会将节点的右子树提升为新的父节点,而原节点成为新父节点的左子节点。通过在链的不同位置执行左旋操作,我们可以构建出具有不同结构的二叉搜索树。

    对于 n 个节点的链,我们最多需要 n-1 次左旋操作来调整链的形状。这是因为每次左旋操作都会改变链的一个节点的位置,而我们有 n-1 个节点需要调整。

综上所述,通过至多 n-1 次右旋和至多 n-1 次左旋,我们可以将任何一棵含有 n 个节点的二叉搜索树转变为其他任何一棵含有 n 个节点的二叉搜索树。总共需要的旋转次数为 O(n)。

在 Go 语言中,我们不需要编写具体的代码来证明这一点,因为这是一个关于二叉搜索树旋转操作的理论性质。在实际的二叉搜索树实现中,我们通常会提供左旋和右旋的函数,以便在需要时调整树的结构。

在这里插入图片描述

混元:

任何一棵含 n 个结点的二叉搜索树可以通过 O(n) 次旋转,转变为其他任何一棵含 n 个结点的二叉搜索树。这个结论基于二叉搜索树的性质和旋转操作的定义。

首先,我们先证明至多 n-1 次右旋足以将树转变为一条右侧伸展的链。我们可以通过以下方式证明这个结论:

  1. 在二叉搜索树中,每个节点的左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。因此,如果我们将二叉搜索树中的每个节点的右子节点进行右旋,那么所有的节点都会按照从小到大的顺序排列在一条链上。

  2. 对于一棵含有 n 个结点的二叉搜索树,我们可以选择从任意节点开始进行右旋操作。由于每个节点的右子节点可以进行右旋,所以我们可以进行 n-1 次右旋操作,将整个树变为一条右侧伸展的链。

接下来,我们需要证明通过 O(n) 次旋转,我们可以将任何一棵含 n 个结点的二叉搜索树转变为其他任何一棵含 n 个结点的二叉搜索树。我们可以通过以下方式证明这个结论:

  1. 对于任意两棵含 n 个结点的二叉搜索树 T1 和 T2,我们可以通过一系列的旋转操作将 T1 转变为 T2。具体操作如下:
  • 找到 T1 和 T2 中最深的共同的祖先节点 P。

  • 将 P 的左子树进行左旋转操作,将其变为 P 的右子树。

  • 将 P 的右子树进行右旋转操作,将其变为 P 的左子树。

  • 将 P 的左右子树的根节点进行右旋

在这里插入图片描述

这篇关于文心一言 VS 讯飞星火 VS chatgpt (171)-- 算法导论13.2 4题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/569180

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

AI绘图怎么变现?想做点副业的小白必看!

在科技飞速发展的今天,AI绘图作为一种新兴技术,不仅改变了艺术创作的方式,也为创作者提供了多种变现途径。本文将详细探讨几种常见的AI绘图变现方式,帮助创作者更好地利用这一技术实现经济收益。 更多实操教程和AI绘画工具,可以扫描下方,免费获取 定制服务:个性化的创意商机 个性化定制 AI绘图技术能够根据用户需求生成个性化的头像、壁纸、插画等作品。例如,姓氏头像在电商平台上非常受欢迎,

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

Andrej Karpathy最新采访:认知核心模型10亿参数就够了,AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人,AI大神Andrej Karpathy,曾是OpenAI联合创始人之一,特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ,宣布将长期致力于AI原生教育。 近日,Andrej Karpathy接受了No Priors(投资博客)的采访,与硅谷知名投资人 Sara Guo 和 Elad G

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig