- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
以下代码是根据 CLRS ( Corman, Leiserson, Rivest, Stein — 'Introduction to Algorithms' ) 教科书进行归并排序的。
我无法确定正在发生的错误,尽管我知道 mergesort()
函数中发生了一些错误。我认为 merge()
在功能上是完整的。
/* Merge sort as per CLRS */
#include <stdio.h>
#include <stdlib.h>
void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1+1)*sizeof(int));
int* ri = malloc((n2+1)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
l[i] = a[p+i-1];
for(i = 0 ; i < n2 ; i++)
ri[i] = a[q+i];
l[n1] = 9999;
ri[n2] = 9999;
i = 0;
j = 0;
int k;
for ( k = p ; k <= r ; k++){
if( l[i] < ri[j] ){
a[k] = l[i];
i++;
}
else{
a[k] = ri[j];
j++;
}
}
}
void mergeSort(int* a,int p,int r){
if( p < r){
int q = ( p + r ) / 2;
mergeSort(a,p,q);
mergeSort(a,p+1,r);
merge(a,p,q,r);
}
else return;
}
int main(int argc, char* argv[]){
int a[] = {9,21,4,15,1,3};
mergeSort(a,0,5);
int i;
for( i = 0 ; i < 6 ; i++){
printf("%d ",a[i]);
}
return 0;
}
最佳答案
void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1+1)*sizeof(int));
int* ri = malloc((n2+1)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
l[i] = a[p+i-1];
for(i = 0 ; i < n2 ; i++)
ri[i] = a[q+i];
您正在编写从索引 p-1
到索引 q-1
到 l
的元素,以及从索引 的元素q
到 r-1
到 ri
。如果 p == 0
,则您访问越界。
但是,您希望对从索引 p
到 r
的元素进行排序。
void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1)*sizeof(int));
int* ri = malloc((n2)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
l[i] = a[p+i];
for(i = 0 ; i < n2 ; i++)
ri[i] = a[q+i+1];
此外,您应该检查两个索引 i
和 j
是否小于相应的结束索引 n1
resp。 n2
,当一个到达其部分的末尾时,将另一部分的剩余部分复制到数组中。如果数组包含大量条目,则保护值会严重失败。
while(i < n1 && j < n2) {
if (ri[j] < l[i]) {
a[k++] = ri[j++];
} else {
a[k++] = l[i++];
}
}
while(i < n1) {
a[k++] = l[i++];
}
while(j < n2) {
a[k++] = ri[j++];
}
关于c - 基于CLRS教科书的归并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14243232/
我正在根据 CLRS 用 C 实现堆排序算法。但是我无法获得排序的输出。您能看一下并告诉我我的代码有什么问题吗?函数 maxheap 和 buildmaxheap 有效。我无法弄清楚代码有什么问题。
我正在尝试 CLRS 中给出的 QuickSort 实现,但它给出了数组索引越界异常。以下是方法。从 main 调用数组,随机生成 10 个元素的数组。 public static String qu
我使用 CLRS 作为对算法的介绍。我正在尝试用 Python 实现书中用伪代码编写的算法。但是,我遇到了问题,因为这本书从 1 开始索引。这就是我实现合并排序的方式,但它无法正常工作: def Me
我正在尝试解决这个问题(CLRS,第 3 版,练习 11.2-1): Suppose we use a hash function h to hash n distinct keys into an
我在 page 47 上看到这段话的 Introduction to Algorithms by Cormen et al. : The number of anonymous functions i
这是我正在寻找答案的问题: 数组 A[1...n] 包含从 0 到 n 除了 1 之外的所有整数。很容易确定丢失的O(n) 时间内的整数通过使用辅助数组 B[0...n] 来记录哪些数字出现在 A 中
我目前正在通过 CLRS 并有一个快速问题。顶点相等性是如何定义的?我遇到了 的问题和 . u != v 是否意味着 u 和 v 不相邻?我认为这只是暗示 u 和 v 不是指同一个顶点?难道 u 和
我正在尝试实现经典 CLRS 书中给出的快速排序算法。我已经在我的 C# 程序中完全逐行实现了它。但是输出是未排序的。以下是我的完整代码以及输出: using System; namespace cl
这是 CLRS 问题。问题来自 CLRS 书的第三版:5-2-b。 随机搜索是一种算法,您必须随机选择一个元素并将其与搜索到的元素进行比较。如果等于,我们需要停止。现在,假设您正好有一个索引为 i 的
我是一名自学计算机科学专业的学生。现在我正在阅读 CLRS,我做了 2.2-2 练习,它是关于选择排序的。 First array subscript is 1. 我写的伪代码是: FOR i=1 t
您好,我正在阅读有关 CLRS 通用哈希的章节。 第 234 页 推论 11.4 Using universal hashing and collision resolution by chainin
不确定我是否应该把它放在 math stackexchange 上,但是哦,好吧。 在 CLRS 第 300 页... Theorem 12.4 The expected height of a ra
我最近试图通过 CLRS 求解一些递归关系,并且在求解这些方程时我注意到了一个奇怪的细微差别。我不知道你们中的任何人是否注意到它,或者理论冠军可以对此进行更多说明。 (我也拥有计算机科学学位,但没有理
我正在尝试在java中实现合并排序,并且我已经按照CLRS书中给出的算法编写了代码。当我尝试运行代码时,我继续遇到数组越界异常。老实说,我不明白我在这里犯了什么错误。 package mergesor
我目前正在阅读 CLRS 的算法导论的第二章,我遇到了一个奇怪的练习。它要求我对插入排序进行排序,以便不增加而不是减少。 所以我假设对于一个给定的数组 A = { 91, 23, 24 ,54, 23
CLRS - Introduction to Algorithms 中的定理 22.10说是 In a depth first search of an undirected graph G, eve
对于“切杆”问题: Given a rod of length n inches and an array of prices that contains prices of all pieces o
我正在尝试从 clrs 书中实现队列,但它没有按预期工作。我的代码有什么问题? 会不会是队列大小或入队操作的问题? 但是,很明显队列上的入队操作没有按预期工作。这是我的代码: class Queue:
我正在尝试在 python 中实现快速排序。 CLRS算法版本。 这是我写的。我认为除了列表的中间元素外,它在大多数情况下都运行良好。 有人可以帮忙吗? #! /usr/bin/python #qui
我一直在阅读 Introduction To Algorithms 中的 Rabin Karp 算法。除以下内容外,一切都有意义。 In general, with a d-ary alphabet
我是一名优秀的程序员,十分优秀!