合并排序和选择排序所需的比较总数
合并排序和选择排序是两种常见的排序算法。
合并排序（Merge Sort）是一种分治算法，它将待排序的数组不断地分割成更小的子数组，直到每个子数组只有一个元素，然后再将这些子数组两两合并，直到最终得到一个有序的数组。合并排序的时间复杂度为O(nlogn)。
选择排序（Selection Sort）是一种简单直观的排序算法，它每次从待排序的数组中选择最小的元素，然后将其放到已排序部分的末尾。选择排序的时间复杂度为O(n^2)。
对于合并排序，比较总数取决于数组的大小和递归的次数。在每一次合并的过程中，需要比较的次数为两个子数组的长度之和。因此，合并排序的比较总数可以表示为：
比较总数 = 数组长度 * log2(数组长度)
对于选择排序，比较总数取决于数组的大小。在每一次选择最小元素的过程中，需要比较的次数为剩余未排序元素的个数。因此，选择排序的比较总数可以表示为：
比较总数 = 数组长度 * (数组长度 - 1) / 2
综上所述，合并排序和选择排序所需的比较总数可以根据上述公式计算得出。
腾讯云提供了多种云计算相关产品，其中包括云服务器、云数据库、云存储等。这些产品可以帮助用户快速搭建和管理云计算环境，提供稳定可靠的计算、存储和数据库服务。具体产品介绍和相关链接如下：
- 云服务器（CVM）：提供弹性计算能力，支持多种操作系统和应用场景。了解更多：云服务器产品介绍
- 云数据库（CDB）：提供高性能、可扩展的数据库服务，支持主流数据库引擎。了解更多：云数据库产品介绍
- 云存储（COS）：提供安全可靠的对象存储服务，适用于各种数据存储和分发场景。了解更多：云存储产品介绍
以上是腾讯云提供的一些与云计算相关的产品，可以根据具体需求选择适合的产品来支持合并排序和选择排序等应用场景。
相关·内容
1回答
我认为这个问题的答案应该是16 is，以下是我的计算方法：
一个整数是32位
在java中，整数的范围为-2^31到2^31-1，因此整数总数为2^32。
我们需要一个大小为2^32的int数组来执行桶排序。
所以我得到了32位* 2^32 =16 32的结果。
有人能告诉我这是否正确吗？因为我发现有人说这个应该是4GB。我不知道4GB是如何计算出来的。
可以找到一个例子：
浏览 2提问于2016-04-01得票数 0
7回答
给定包含15、3、9和8条记录的4个排序文件，将它们合并到单个排序文件中所需的比较总数是多少？
假设我们对此使用了合并步骤(从合并排序)。
我知道执行合并步骤需要O(N)时间。但是，它进行了多少次比较？
浏览 0提问于2011-09-06得票数 2
回答已采纳
对不起，这个问题可能是新程序员问的一个愚蠢的问题(我自己：)。从以下链接:合并排序的时间复杂度为T(n) = 2*T(n/2) + cn
以下是我的问题：
2*T(n/2)表示n个输入的左部分(从索引0到索引中间)和右边部分(从索引middle+1到n的最后一个元素)所花费的时间？cn表示花费的时间吗？cn表示n个输入的“征服”过程，因为我们需要遍历所有的n个输入才能将它们按正确的顺序排列，对吗？？
浏览 1提问于2019-11-13得票数 0
回答已采纳
2回答
如果以前已经回答过这个问题，请给我指出正确的方向！
所以，我一直在闲逛，所以在阅读有关排序的文章时，我已经有好几次了。然而，我想知道，选择一个好的单链表排序算法与双链表排序算法(以及与数组结构相比也是链接结构)之间的主要区别是什么？
我知道(假设我们使用的是面向对象语言)，类型关系到要排序的元素，等等(原始类型通常比复杂对象更快)。我在比较Java字符串和整数。
据我所知，在处理链接结构时，我们可能应该排除快速排序和插入排序，因为它们经常处理索引问题。
这个问题可能很糟糕，但正如我所提到的，请告诉我另一个来源，在那里我可以阅读有关选择正确算法的内容(而不是如何实现一个算法)。
浏览 0提问于2018-02-15得票数 1
回答已采纳
5回答
在许多情况下，快速排序比合并排序要好得多。但是，何时合并排序可能比快速排序更好的解决方案呢？
例如，当数据无法同时加载到内存时，合并排序比快速排序更有效。还有其他的案子吗？
编辑:答案的建议重复的问题列表，所有的优点，快速排序比合并排序。我在这里询问使用合并排序比使用快速排序更有利的可能案例和应用程序。
浏览 1提问于2015-03-23得票数 36
回答已采纳
4回答
这是我最近在网上找到的一个面试问题：
如果你要实现一个以整数数组作为输入并返回最大值的函数，你会使用冒泡排序还是合并排序来实现这个函数？如果数组大小小于1000怎么办？如果它大于1000呢？
我是这样想的：
首先，使用排序来实现上述功能真的很奇怪。你只需遍历数组一次，就能找到最大的一个。其次，如果必须在两者之间做出选择，那么冒泡排序更好--您不必实现整个冒泡排序过程，只需执行第一遍。它在时间和空间上都优于合并排序。
我的答案中有错误吗？我错过什么了吗？
浏览 2提问于2013-03-08得票数 9
回答已采纳
1回答
我正在处理一个问题，在这个问题中，我需要对数据的80GB进行排序。我只有1GB主内存来对数据进行排序。显然，我们将在这里应用外部排序方法。但我的问题是哪种k-合并排序会更有效？
8路合并后10路合并
5路合并后16路合并
K-合并排序的复杂性是O(nk^2)，其中n是元素数.假设我使用此方法计算复杂性：
8路合并，然后是10路合并
8 way merge - O(n*8^2) => O(64n)
10 way merge - O(8n*10^2) => O(800n)
Total time complexity => O(64n) + O(800n)
5路合
浏览 1提问于2015-12-07得票数 0
回答已采纳
可能重复：
任务是找到一种用最小比较数(非操作)对8个随机数进行排序的方法。我希望我必须使用qSort (将数组除以一半，排序，然后合并等等)。我认为这一定是最快的。对于8个元素的比较数是17，我必须证明没有办法用16 (n - 1)比较对随机数组进行排序。
谢谢
无论如何，也一定是最糟糕的。我正在学习的第一年，所以我不认为我们必须做一些非凡的事情(我学习数学，而不是IT)。我用的那种是合并！提前谢谢。
浏览 3提问于2011-12-29得票数 3
1回答
我使用的是一种合并-插入混合排序，大致如下所示： def hybrid_sort_comparisons(arr, S):
"""
Performs hybrid sort on `arr` with threshold `S`
Returns (arr, number_of_comparisons)
"""
if (len(arr) <= S):
return insertion_sort_comparisons(arr, S)
num = len(arr) //
浏览 27提问于2021-09-06得票数 0
1回答
最近我接触过很多排序算法:从气泡排序到基数排序和计数排序，但是有一个特殊的问题，我不知道做什么是合法的。(我还处于伪代码编写阶段，所以我还没有用代码语言编写algs，也没有运行测试--因此，我对什么是“合法”和什么不合法的安全性有点动摇。)
问题在于对与起始点有关的间隔列表进行排序:例如:对我设计的特定算法排序List1 = [1,4，7，17，5，10]，我需要将它们排序为：[1,4，5，10，7，17]
我想向后做基排序，但我读到基排序是专门用于数字排序的。看起来我也可以用桶排序，但我们在课堂上没有学过桶排序.
Edit1:有一个时间效率我需要担心，所以这就是为什么我不做最简单的解决方案，
浏览 0提问于2013-09-30得票数 0
回答已采纳
1回答
两个列表a和b，使得len(a) + len(b) == 5和merge(a,b)都只进行一次比较。这个大O符号是什么？
浏览 1提问于2018-04-19得票数 2
2回答
摸索时间排序
、、、、
块上有一种(相对)新的排序，叫做Timsort。它曾被用作Python的list.sort，现在将成为。
有和描述了排序的高级属性和一些低级的性能评估，但我很好奇是否有人能提供一些伪代码来确切地说明Timsort正在做什么，以及使它变得灵活的关键因素是什么。(特别是关于被引用的论文“乐观排序和信息理论的复杂性”。)
(另请参阅。)
浏览 2提问于2009-11-14得票数 25
回答已采纳
如果数组长度小于某个阈值，Java6在Arrays.java中的合并排序实现将使用插入排序。这个值被硬编码为7。由于算法是递归的，对于大型数组，这种情况最终会发生很多次。规范的并不这样做，只是一直使用merge-sort，直到列表中只有1个元素。
这是一种优化吗？如果是这样，它应该有什么帮助呢？为什么是7？插入排序(甚至是<=7排序)大大增加了对大型数组进行排序所需的比较次数-因此会增加compareTo()调用速度较慢的排序的开销。
(对于不同的INSERTIONSORT_THRESHOLD值，x轴为size of array，y轴为# of comparisons )
浏览 0提问于2011-07-11得票数 22
回答已采纳
1回答
自下而上合并排序的实现
、、、
据我所知，合并排序是一种遵循划分和征服原则的排序算法，其平均时间复杂度为n(log )。
在这里，我在子数组中划分了大小为n的数组(用长度2初始化)，并通过对子数组进行排序来克服它。然后，我们以2的倍数处理范围，直到它小于数组的长度(即，2,4,8，....i，其中数组的i<length )。
当它超过数组的长度时，函数返回排序数组。
我使用了两个函数来实现合并排序：
Array)If 合并排序(产生数组的子exponentially.Insertion长度小于范围、返回array.Recursion和增加范围exponentially.Insertion排序(使用插入排序对范围内的元素
浏览 2提问于2021-07-18得票数 0
回答已采纳
3回答
根据我(简要地)读到的，Java和Python看起来都在他们的标准库中使用timsort，而C的stdlib中的排序方法被称为qsort，因为它曾经是快速排序。
今天，典型的语言在他们的标准库中实现了什么算法，为什么他们选择这种算法？另外，C语言是否偏离了快速排序？
我知道这个问题缺乏“我面临的实际问题”，对一些人来说似乎是开放的，但知道如何/为什么选择某些算法作为标准似乎非常有用，但相对没有教过。我也觉得似乎是一个深入的答案，解决了特定于语言的问题(数据类型？)和特定于机器的(缓存命中？)将提供更多关于不同语言和算法如何工作的洞察力，而不是uni所关心的解释。
浏览 0提问于2013-05-01得票数 7
以下引用来自页面中的“与其他排序算法的比较”部分
在典型的现代体系结构中，高效的快速排序实现通常优于基于RAM的arrays.citation的合并，另一方面，合并排序是一种稳定的排序，并且在处理慢访问顺序媒体方面更有效。
我的问题：
为什么快速排序优于Mergesort，因为要排序的数据都可以存储在内存中？如果所有需要的数据都被缓存或存储在内存中，那么快速排序和Mergesort都可以访问吗？
为什么Mergesort在处理缓慢访问顺序数据(例如，在要排序的数据不能全部装入内存的情况下从磁盘)时更有效？
(从下面的注释移到这里)，在n个元素的基元数组(数据是顺序的)中。在
浏览 4提问于2017-12-19得票数 14
回答已采纳
1回答
我正在尝试计算我的选择排序算法进行的交换和比较的数量。CountSwaps是一个全局变量。 我尝试在实际的交换方法中实现交换计数，但它给出了相同的输出。 public static void SelectionSort(int[] Array) // descending order
{
int countComps = 0;
int max;
Stopwatch timer = new Stopwatch();
timer.Start();
for (int i = 0; i <= Array.
浏览 12提问于2019-05-03得票数 0
回答已采纳
2回答
Matlab排序算法
、、、
在Matlab中，我一直在研究各种排序算法，如合并、冒泡、快速和桶式排序，并提出了一些问题。它指出插入排序、冒泡排序和快速排序的运行时间为O(n^2)，而合并和桶的运行时间为O(nlog(n))。我想知道，如果最后两个更快，为什么使用前三个中的任何一个。如果列表排序更多/排序更少、更大/更小等等，它们会更快吗?还是还有其他原因？
浏览 1提问于2016-05-28得票数 0
回答已采纳
在快速排序中，如果始终选择关键元素作为中间元素，那么它是否与合并排序相同？
浏览 1提问于2022-04-11得票数 0
1回答
有人能解释一下哪一种比较好吗?它们的时间和空间的复杂性，以及你认为值得知道的任何重要事情。我知道2S1D和2S2D是如何工作的。
浏览 2提问于2018-04-24得票数 0
回答已采纳
我想知道您是否会使用插入或选择一个几乎排序的文件。这两家公司平均进行了多少次互换？我听说过用于选择的N/2和O(n)！我知道插入时必须扫描数组的排序部分，以查找放置新元素的位置，但在选择中，必须扫描数组的整个未排序部分，以找到要添加到未排序子数组开头的下一个元素。
浏览 0提问于2018-12-05得票数 3
回答已采纳
4回答
我试图计算最小生成树算法的运行时。
以下是算法：
我理解步骤从1到3的调整时间，但我真的不明白为什么需要O(E，logE)时间来对边进行非递减排序。
谢谢。
浏览 10提问于2017-04-29得票数 2
回答已采纳
1回答
我试图在一个对象数组中按2列进行分组，并得到一个值的分组和总数。为此，我一直在使用linq，这是代码：
import Enumerate from "linq";
let data = [
{ Phase: "Phase 1", Step: "Step 1", Task: "Task 1", Value: "5" },
{ Phase: "Phase 1", Step: "Step 1", Task: "Task 2", Value: "10" }
浏览 1提问于2020-05-06得票数 1
回答已采纳
这里有一个小分歧的问题，由于我找不到我想要问的问题，所以我的问题如下：
在Cormen的“算法简介”第2节，问题2.1中，选项d要求，如果一个人想要将合并排序和插入排序结合起来，以减少时间，因为插入排序在小规模的输入上可以因为系数较小而更快，方法是将n的输入大小划分为k个片段，然后在这个n/k小块上进行插入，如何选择k？
我的尝试是，考虑组合排序的最坏情况和正常合并排序的最佳情况，然后找一个合适的k作为下界，因为在最坏的情况下，我认为n/k分段将需要k^2/2时间(可能有附加的项，但仅考虑前导系数)，因此总共需要nk/2步骤。另外，使用合并排序将需要nlg(n/k)时间，因此考虑到以下几点：n
浏览 2提问于2022-01-09得票数 0
3回答
给定一个正负数的排序数组(例如：-9，-7，-4，-0.9，1，2，3，8)，我需要按排序顺序输出数组中的元素，其绝对值小于O(N^2)，而不使用任何内置函数。
对于这个简单的问题，有人知道什么可接受的解决方案吗？我正在考虑修改快速排序算法，让它检查元素的abs值。
浏览 1提问于2014-07-08得票数 0
回答已采纳
2回答
从的维基百科页面上，我发现块排序的工作原理是将初始数组分成长度为16的子数组，在O(n)时间内对所有这些子数组进行排序，然后以一种我无法理解的方式合并所有这些块。
例如，考虑一个长度为16的数组，将其分成4个块，每个块的长度为4，并对这些块进行排序，我们得到：
10 1 8 3 4 19 20 13 14 17 8 9 12 18 7 20
10 1 8 3 ----- 4 19 20 13 ----- 14 17 8 9 ----- 12 18 7 20
1 3 8 10 ----- 4 13 19 20 ----- 8 9 14 17 ----- 7 12 18 20
有人能给我解释一下合
浏览 0提问于2014-11-15得票数 6
2回答
我已经看过了这里的所有帖子，似乎找不到一个有效的解决方案。排序是有效的，但它的速度比它应该的速度慢得令人难以置信。下面是代码(我在一个头文件中工作)：
#pragma once
#ifndef DataGen_h
#define DataGen_h
#include "RandomSupport.h"
void merge(long list[], long start, long mid, long end) {
long i = start;
long j = mid + 1;
while (j <= end && i
浏览 1提问于2017-10-09得票数 0
我有两个以竖线分隔的文件，用来比较它们的列。i data...need是主键......
例如：one.dat
123|NY|AA|500
569|NY|A|450
777|OK|B|250
899|OK|C|100
two.dat
569|NY|A+|500
777|OK|A|350
899|OK|B|150
输出应如下所示：
NY column3 1
NY column4 1
OK column3 2
OK column3 2
这意味着纽约的记录..。列III对于匹配的records..for OK有一个差异，records...column 3对于匹配的记录有两个差异...
我想
浏览 0提问于2013-09-25得票数 0
1回答
我真的是一个超级粉丝的无与伦比和记事本++，并使用它在我的工作中的许多比较，每天的基础上。我正在使用最新版本的软件。所以这是我的问题。我有两个文本文件，其中文本文件1有以下(帐户ID)，这个数字是我真正想要比较的
Text|Text|1234532|Text
Text|Text|1234678|Text
Text|Text|2345612|Text
Text|Text|3427891|Text
Text|Text|0235719|Text
Text|Text|3421482|Text
现在是我的第二个文本fIle 2有下面的(帐户ID)，这个数字是我真正想要比较的
Text|Text|0235
浏览 5提问于2017-02-01得票数 2
1回答
合并排序的最坏情况复杂性为O(logN)和Quick有O(N^2)，因此理论上合并排序应该比快速排序更好。但我听说，由于一些复制开销，大多数情况下，快速排序优于合并排序。。
然后我决定实现和测试，下面是我用C语言编写的完整源代码，
来源
#include <stdio.h>
#include <time.h>
#define SZ 10000000
#define MOD 10000007
#define i64 long long int
i64 nums[SZ];
i64 L[SZ], R[SZ];
i64 seed = 0xff;
i64 srand(){
浏览 2提问于2018-10-02得票数 3
回答已采纳
4回答
O(nlogn)就地排序算法
、、、、
这个问题是在我的计算机科学入门期中考试准备的。
有一种算法可以在O(n)时间内找到列表中的kth元素，并假定它已经就位。使用该算法，编写一个在最坏情况下运行的就地排序算法O(n*log(n))，并证明了它的有效性。既然这个算法存在，为什么还会使用mergesort呢？
我假设我必须编写一些快速排序算法的替代形式，这是O(n^2)的最坏情况，因为合并排序不是就地算法。让我困惑的是在列表中找到kth元素的给定算法。通过数组的元素进行简单的循环迭代不是一个O(n)算法吗？
如果所提供的算法不改变执行时间内的任何内容，它如何能使排序算法的运行时间有任何不同？我不知道如何使用快速排序，插入排序或
浏览 3提问于2015-10-21得票数 2
1回答
我为我的应用程序实现了二次排序。
File-1 File-2 File-3
------ ------ ------
name,pos,r,value name,pos,r,value name,pos,r,value
aa,1,0,123 aa,2,1,1 aa,3,1,11
bb,1,0,2
浏览 1提问于2017-11-22得票数 0
4回答
我有一个需要使用可视化框架的应用程序。我目前倾向于在Java桌面应用中使用Processing。
问题:我有需要可视化的~500k+状态向量。4D点- XYZ和时间(类似GPS)
我需要能够选择时间片快速和容易，也有能力在时间上播放它们。我可以使用平面文件或db来更改输入。
所以问题是:什么样的数据结构最适合我的需求？我要将文件读入数组列表吗？哈希图？还是内存中的数据库？还是别的什么？
在3D可视化中，性能是必须的。时间段超过8个小时。因此，并不是所有的数据都会同时显示。
有没有人尝试过将创造性的编码框架用于这种类型的使用？有什么建议吗？
谢谢!
浏览 0提问于2010-08-06得票数 3
回答已采纳
我刚刚写了一篇关于不同排序算法的效率和有用性的文章。我的结论是，在对完全随机的列表进行排序时，合并排序和快速排序要好得多。我只是想问，在什么情况下，这种情况下较慢的排序算法(冒泡排序和选择排序)会比快速排序和合并排序更有用或一样有用。
浏览 2提问于2019-10-20得票数 0
1回答
我有一个对象向量v，它使用自定义函数sortproc排序。
std::sort(v.begin(), v.end(), sortproc);
在对数组进行排序之前，我想事先知道sortproc将被调用多少次。
我试过什么？我试着克隆载体，然后对拷贝进行排序，并计算出sortproc被调用了多少次。我是通过增加计数器来做到这一点的。然后，在对副本进行排序之后，我读取计数器的值，并再次对原始向量进行排序。这是可行的，但效率很低，因为它做了两次整个工作。是否有可能以更有效的方式做到这一点？
浏览 0提问于2013-12-07得票数 0
回答已采纳
在大多数需要排序数据的场景中，选择比较排序。诸如合并排序、快速排序、插入排序和其他比较排序等技术可以处理不同的数据类型和效率，其下限为O(nLog(n))。
我的问题是
基于比较的排序技术是否有任何限制？
任何一种使用非比较排序技术的场景？
干杯
浏览 2提问于2009-04-26得票数 5
回答已采纳
3回答
人们普遍认为，对于足够小的数组，插入排序是最好的。例如，对最多64个元素的数组使用(二进制)插入排序；来自：
一些分而治之的算法，如快速排序和合并排序，通过递归地将列表划分为较小的子列表，然后排序。在实践中，这些算法的一个有用的优化是使用插入排序来排序小的子列表，因为插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现的不同而不同，但通常在8-20个元素之间。
这是真的吗？还有更好的选择吗？
如果这在很大程度上取决于平台，我对.NET最感兴趣。
浏览 6提问于2009-08-14得票数 4
回答已采纳
我有一个数组，在这个数组中，我希望找出我需要做的最小值数，以便将数组更改为递增或递减顺序。
例如：
a = [1,2,5,6,5,7]
In above array, a[4]=5 which is less than a[3]=6. So I can add 1 to 5 to make it 6 so array becomes a=[1,2,5,6,6,7]. It is ok if I have same values consecutively.
我已经写了下面的程序，但我不确定这是否工作良好的所有情况。
public int process(List<Integer>
浏览 1提问于2018-09-06得票数 0
我刚从Tableau开始，如果在for循环中，我想做一个计数。
我有以下变量：
CityUserRound:采用A值或BAmount值
我希望有一个countif函数，显示在一个给定的城市中，有多少用户在第A轮和第B轮中都收到了任何正数。
在我的仪表板中，每一行代表一个城市，我希望有一个列显示每个城市在两轮中接收的用户总数。
谢谢!
浏览 10提问于2020-12-16得票数 0
回答已采纳
如果有n个范围，其中的范围类似于[1,4.5]，那么如何在O(nlogn)时间中找到任何索引包含另一个索引？注意:如果是[x,y]和b <= y，那么[a,b]将完全包含x >= a。
这似乎可以类似地进行合并排序，在其中您可以检查任何范围是否包含在范围总数的每一半中的另一个范围中，然后比较两个区域中的任何一个范围是否包含另一半的范围。我的问题是，我找不到一个O(n)的方法来完成最后一部分。我想我会以某种方式组合一些范围，但我想不出怎么做。
浏览 3提问于2015-10-02得票数 3
回答已采纳
6回答
在这两个算法中，你所做的就是把你的结构递归地一分为二，然后以正确的顺序构建你的结构，这样说对吗？
那么，有什么不同呢？
编辑:我找到了在快速排序中实现分区的以下算法，但我并不真正理解它是如何工作的，特别是使用(hi + low) >>> 1作为参数的swop行！有人能理解这一点吗？
private static int partition( int[] items, int lo, int hi )
{
int destination = lo;
swop( items, (hi + lo) >>> 1, hi );
// The
浏览 0提问于2011-04-19得票数 5
您将看到一个由n个请求组成的数组A，请求2010年奥运会门票。该数组按请求的时间排序，因此A(1)是第一个到达的，A(2)是第二个到达的，依此类推。每个请求都包含一个十位数的电话号码。为了公平起见，奥运会组织者规定每个电话号码只能有一个请求。已经注意到，数组A包含来自某些电话号码的一个以上请求。编写一个O(nlogn)时间分割和征服算法，从A中删除来自同一电话号码的所有请求，除了第一个接收到的请求。最终输出应该是包含来自唯一电话号码的m<=n请求的数组A。此外，A中的请求应该保持与删除重复之前相同的顺序。
我知道如果数组是按电话号码排序的，那么如何做到这一点，但是，当数组按请求时间排序时
浏览 3提问于2013-10-29得票数 1
回答已采纳
以下是我的问题：
我想在目标表中更新与原点不匹配的行，下面是一个示例：
表A(产地)
1234 3456 4235 5664 2345 2349
表B(目的地)
1234 3456 4235 5664 2345
正如您所看到的，行"2349“不是在目标表(表B)中，所以有一种使用ssis的方法(我正在使用宾得数据集成)来‘说’：”嘿！查看表A和表B之间的非匹配行，然后用不匹配行更新表B？
浏览 0提问于2021-10-22得票数 0
回答已采纳
因此，对于拆分时的合并排序，我将使用
HGFEDCBA
HG FE DC BA
H G F E D C B A
用于合并，而不是
GH EF DC AB
EFGH ABCD
ABCDEFGH
好呀
H G F E D C B A
GH F E D C B A
FGH E D C B A
EFGH D C B A
DEFGH C B A
CDEFGH B A
CBDEFGH A
ABCDEFGH
我能想到的唯一一件事是，合并排序通常是递归实现的，如果使用递归进行拆分，使用第一种方法合并会更容易。
浏览 1提问于2020-01-15得票数 1
1回答
我真的不知道如何找到算法的递归方程，我已经读过关于这个主题的其他问题，但有一些东西我仍然不明白。例如，在以下代码中(实际上是伪代码: )：
MergeSort(list "L" of "n" elements):
if n=<1 then return L
L1 <- MergeSort(L1... n/2)
L2 <- MergeSort(L(n/2 +1) ... n)
L <- Merge(L1, L2)
return L
递推方程为: T(1) =2T(N)= c1 + c2.n + 2T(n/2)
我不明白什么是c1，c2和
浏览 2提问于2013-06-09得票数 1
回答已采纳
我想知道std::sort和std::stable_sort在功能、内存和硬件方面有什么不同？提到“将范围[first，last]中的元素按升序排序，就像排序一样，但stable_sort保留了具有相等值的元素的相对顺序。”，但这对我来说没有意义。什么是“相对顺序”和“等价值”？
浏览 0提问于2014-06-02得票数 28
2回答
我开始理解当排序时，比方说LinkedList，最好使用合并排序，因为当你想把一些东西放在列表的中间时，你需要O(1) (常量)时间和O(1)内存。因此，可以在不占用额外空间的情况下进行合并排序。
我的问题是:应该在ArrayList上使用哪种排序算法？排序的数据类型重要吗？
如果我对LinkedList的理解是错误的，请纠正我，或者让我知道我是否遗漏了什么(例如，使用merge的一些参数)。
浏览 1提问于2018-02-20得票数 0
正如问题中提到的，需要找到数组中的(i，j)对的总数，以便
(1) **i<j**
(2) **a[i]>a[j]**
其中i和j是数组的索引。没有空间限制。
我的问题是
1) Is there any approach which takes less than O(N^2) time?
2) if so what is least complexity ?
3) How do we prove that ?
我希望我把问题说清楚了。
我的方法如下
做这个问题的一种方法是使用暴力前，这需要O(N^2)时间。
但我认为这个问题应该有一个更好的优化解决方案-至少O(Nlog
浏览 0提问于2012-10-31得票数 9
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
