- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我是合并排序新手,正在尝试创建一个。我的合并排序没有对我发送的数组进行排序,我不明白为什么。这是所有代码的链接 http://pastebin.com/M4RUzhUa
这是我的合并排序函数
void merge_sort(int array[], int low, int high) {
int middle = (low + high) / 2;
if(low < high) {
merge_sort(array, low, middle);
merge_sort(array, middle+1, high);
merge(array, low, middle, high);
}
}
这是我的(更新的)合并函数
void merge(int array[], int low, int middle, int high) {
int size,left,right,i, j;
size = high - low + 1;
int array1[high];
left = low;
right = middle + 1;
i = low;
while ((left<=middle) && (right<=high)) {
if(array[left] < array[right]) {
array1[i] = array[left];
left++;
i++;
}
else {
array1[i] = array[right];
right++;
i++;
}
}
while (left <= middle) {
array1[i] = array[left];
left++;
i++;
}
while (right <= high) {
array1[i] = array[right];
right++;
i++;
}
for (j = low; j < i; j++) {
array[j] = array1[j];
}
}
在我的程序中,输入数组是
93215
输出是
01235
第一个元素发生了一些我无法弄清楚的事情
最佳答案
更新代码的新评论:
看起来您正轻快地越过数组的末尾。测试的一种方法是在数组周围添加一些保护变量,如下所示:
#define NUM_OF_INTS 5
#define DEBUG 1
int main()
{
int frontguard=-500;
int numbers[NUM_OF_INTS];
int backguard=-600;
int i;
srand(0);
//Fill the array
for( i = 0; i < NUM_OF_INTS; i++ )
{
//Use random numbers
//numbers[i] = rand()%10000;
//Use reverse sorted list
numbers[i] = NUM_OF_INTS-i;
//Use sorted list
//numbers[i] = i;
}
if (DEBUG == 1) printf( "Unsorted list\n" );
if (DEBUG == 1) printarray( numbers, 0, NUM_OF_INTS/2, NUM_OF_INTS );
if (DEBUG == 1) printf( "frontguard=%04d, backguard=%04d\n", frontguard, backguard);
merge_sort( numbers, 0, NUM_OF_INTS );
if (DEBUG == 1 ) printf( "\nSorted list\n");
if (DEBUG == 1) printarray( numbers, 0, NUM_OF_INTS/2, NUM_OF_INTS );
if (DEBUG == 1) printf( "frontguard=%04d, backguard=%04d\n", frontguard, backguard);
return 0;
}
printarray
是我编写的一个辅助函数,用于 pretty-print 数组中发生的情况
void printarray( const int arr[], const int low, const int middle, const int high )
{
int i;
for (i = low; i < high; i++ )
{
if( i == low )
printf( " L%04d", i );
else if( i == middle )
printf( " M%04d", i );
else if( i == (high-1) )
printf( " H%04d", i );
else
printf( " *%04d", i );
}
printf( "\n" );
for( i = low; i < high; i++ )
printf( " %04d", arr[i] );
printf( "\n" );
}
如果您没有/想要调试器,通常必须创建一些辅助调试函数(例如此函数)才能使代码正常工作。不要害怕编写一些一次性代码来了解您的代码在做什么!在这种情况下,我不需要L/M/H这行,但花时间还是值得的。我建议将这些类型的函数留在代码中,并进行注释(使用#define,例如 DEBUG),以防将来的维护人员需要它们。
这是函数的原样输出:
Unsorted list
L0000 *0001 M0002 *0003 H0004
0005 0004 0003 0002 0001
frontguard=-500, backguard=-600
Sorted list
L0000 *0001 M0002 *0003 H0004
-600 0001 0002 0003 0004
frontguard=-500, backguard=0005
您可以看到backguard
被覆盖并“窃取”到您的输出中。 (顺便说一句,这种行为在不同的 CPU 架构、C 实现和运行细节上可能有所不同。)问题是您使用 high 从
作为数组的大小(在本例中为 5),但是 main()
调用 merge_sort
merge_sort
期望 high
是数组中的最后一个有效索引(numbers[4] 是最后一个数组项)。将 main()
修改为
merge_sort( numbers, 0, NUM_OF_INTS-1 );
并针对已排序、反向排序和随机数字数组进行测试。
<小时/>原评论:首先,您应该收到段错误,而不仅仅是错误排序的数据。
size = high - low + 1;
//create a helper array and set it equal to the input array
int array1[size];
for (i = low; i <= high; i++) {
array1[i] = array[i];
}
想想当 low 不为零时会发生什么。假设 l=6、m=6、h=7。您将辅助数组的大小设置为 2,但您使用 i=6 来访问它,因此您正在破坏堆栈。
最简单的解决方法是声明 int array1[high];
。它的内存效率很低,但它使其余代码保持简单,这确实更有值(value)。
其次,您的 for 循环索引超出了数组末尾,您需要使用 i < high。在 C 中,数组从 0 开始,因此大小为 5 的数组的有效位置为 0,1,2,3,4。您的代码将尝试从 array[5] 读取(可能不是致命的),并写入 array1[5] (很可能是致命的)。我敢打赌,这就是为什么你在 size 语句中有 +1,因为否则你已经超出了 array1 的末尾。
for (i = low; i < high; i++) {
这些将修复您的段错误。修复此问题后,您的输出中仍然会收到垃圾数据。
中间的 else-if 语句永远不会被执行 - 任何等效的数据都将被第一个 if 语句覆盖。
您的 while 循环无法正确处理退化情况。它需要检测两个列表中的一个是否已被完全消耗,如果是,则复制另一个列表的其余部分。
此外,while 循环需要单独的跟踪器变量来表示低、中和输出数组。您不能将 currentLow 同时用于 low 数组和输出数组。
最后,在测试排序时,随机数据是不够的(尤其是大小为 5),您应该始终测试已排序和反向排序列表的完全退化情况。
关于C - 合并排序的合并部分,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22208106/
我有几个长度不等的 vector ,我想对其进行cbind。我将 vector 放入列表中,并尝试结合使用do.call(cbind, ...): nm <- list(1:8, 3:8, 1:5)
合并(合并)两个 JSONObjects 的最佳方式是什么? JSONObject o1 = { "one": "1", "two": "2", "three": "3" }
我在一个表中有许多空间实体,其中有一个名为 Boundaries 的 geometry 字段。我想生成一个具有简化形状/几何图形的 GeoJson 文件。 这是我的第一次尝试: var entitie
谁能说出为什么这个选择返回 3.0 而不是 3.5: SELECT coalesce(1.0*(7/2),0) as foo 这个返回 3: SELECT coalesce(7/2,0) as foo
首先抱歉,也许这个问题已经提出,但我找不到任何可以帮助我的东西,可能是因为我对 XSLT 缺乏了解。 我有以下 XML: 0 OK
有时用户会使用 Windows 资源管理器复制文件并在他们应该执行 svn 存储库级别的复制或合并时提交它们。因此,SVN 没有正确跟踪这些变化。一旦我发现这一点,损坏显然已经完成,并且可能已经对相关
我想组合/堆叠 2 个不同列的值并获得唯一值。 如果范围相邻,则可以正常工作。例如: =UNIQUE(FILTERXML(""&SUBSTITUTE(TEXTJOIN(",",TRUE,TRANSPO
使用iTextSharp,如何将多个PDF合并为一个PDF,而又不丢失每个PDF中的“表单字段”及其属性? (我希望有一个使用来自数据库的流的示例,但文件系统也可以) 我发现this code可以正常
是否有一个合并函数可以优先考虑公共(public)变量中的非缺失值? 考虑以下示例。 首先,我们生成两个 data.frames,它们具有相同的 ID,但在特定变量上有互补的缺失值: set.seed
我们正在尝试实现 ALM Rangers 在最新的 Visual Studio TFS Branching and Merging Guide 中描述的“基本双分支计划”。 .从指导: The bas
我在不同目录(3个不同名称)中有很多(3个只是一个例子)文本文件,如下所示: 目录:A,文件名:run.txt 格式:txt制表符分隔 ; file one 10 0.2 0.5 0.
我有一张包含学生等级关系的表: Student Grade StartDate EndDate 1 1 09/01/2009 NULL 2
我在学习 https://www.doctrine-project.org/projects/doctrine-orm/en/2.6/reference/working-with-associatio
我觉得我有世界上最简单的 SVN 用例: 我有一个文件,Test.java在 trunk SVN的。 我分行trunk至 dev-branch . 我搬家Test.java进入 com/mycompa
我有两个数据框,其中一些列名称相同,而另一些列名称不同。数据框看起来像这样: df1 ID hello world hockey soccer 1 1 NA NA
Elasticsearch 中是否缺少以扁平化形式(多个子/子aggs)返回结果的方法? 例如,当前我正在尝试获取所有产品类型及其状态(在线/离线)。 这就是我最终得到的: aggs [ { key:
如何合并如下所示的 map : Map1 = Map(1 -> Class1(1), 2 -> Class1(2)) Map2 = Map(2 -> Class2(1), 3 -> Class2(2)
我试图通过从netezza服务器导入数据来合并两个数据集。 以下是数据集,其数字为,ID为,字母为,名称为: 下表都是使用命令从netezza导入的: sqoop import --connect n
我有两个数组 $array1 = array('first', 'second', 'third', 'fourth'); $array2 = array('first', 'third', 'fou
我正在 SQL Server 中运行合并。在我的更新中,我只想在值发生更改时更新该行。有一个版本行在每次更新时都会递增。下面是一个例子: MERGE Employee as tgt USING (SE
我是一名优秀的程序员,十分优秀!