作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我一直在经历Introduction to Algorithms ,并一直尝试用 C 语言实现MERGE-SORT
算法,以更好地理解它。
本书提供了两个伪代码:
和
虽然我确实理解了上述过程,但在实现过程中我一定遗漏了一些东西。
我肯定在伪代码中遗漏了一些东西,但还无法弄清楚。任何关于为什么会发生这种情况的建议将不胜感激。
编辑:更新代码和输出
/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>
void MERGE(int [], int , int , int );
void printArray(int [], int );
void MERGE_SORT(int [], int , int );
int main(void)
{
int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
int arr_size = sizeof(A) / sizeof(A[0]);
printf("Given array is \n");
printArray(A, arr_size);
MERGE_SORT(A, 0, arr_size); //Fixed: Index to start from zero
printf("\nSorted array is \n");
printArray(A, arr_size);
return 0;
}
void MERGE(int A[], int p, int q, int r)
{
int i = 0;
int j = 0;
int n1 = q - p + 1; //Computing length of sub-array 1
int n2 = r - q; //Computing length of sub-array 2
int *L = malloc((n1 + 2) * sizeof(*L + 1)); //Creating Left array
int *R = malloc((n2 + 2) * sizeof(*R + 1)); //Creating Right array
for (int i = 0; i <= n1; i++) { //Fixed: <=, i start from 0
L[i] = A[p + i - 1];
}
for (int j = 0; j <= n2; j++) { //Fixed: <=, i start from 0
R[j] = A[q + j];
}
L[n1 + 1] = 99; //Placing Sentinel at the end of array
R[n2 + 1] = 99;
i = 1;
j = 1;
/*Prior to the first iteration k = p, so the subarray is empty.
Both L[i] and R[j] are the smallest elements of their arrays and have not
been copied back to A*/
for (int k = p; k <= r; k++) { //Fixed: <=
if (L[i] <= R[j]) {
A[k] = L[i];
i++;
}
else { //Fixed: Assignment and not condition check for A[k]
A[k] = R[j];
j++;
}
}
free(L);
free(R);
}
void MERGE_SORT(int A[], int p, int r)
{
//During first iteration p = 1 & r = 8
if (p < r) {
int q = (p + r) / 2;
MERGE_SORT(A, p, q);
MERGE_SORT(A, q + 1, r);
MERGE(A, p, q, r);
}
}
/* Function to print an array */
void printArray(int Arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", Arr[i]);
printf("\n");
}
最佳答案
查看伪代码,发现有些东西写错了。
1.需要注意数组索引从0或1开始
2. for循环中的最后一部分合并实际上是一个赋值而不是条件检查。
编辑:已更新代码以修复错误变量 A 周围的堆栈已损坏
请在此处找到更正的代码(查找//Fixed 进行修复)
/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>
void MERGE(A, p, q, r);
void printArray(Arr, size);
void MERGE_SORT(A, p, r);
int main(void)
{
int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
int arr_size = sizeof(A) / sizeof(A[0]);
printf("Given array is \n");
printArray(A, arr_size);
MERGE_SORT(A, 0, arr_size - 1); //Fixed: Index to start from zero, arr_size - 1
printf("\nSorted array is \n");
printArray(A, arr_size);
return 0;
}
void MERGE(int A[], int p, int q, int r)
{
int i = 0;
int j = 0;
int n1 = q - p + 1; //Computing length of sub-array 1
int n2 = r - q; //Computing length of sub-array 2
int *L = malloc((n1+1) * sizeof(*L+1)); //Creating Left array
int *R = malloc((n2+1) * sizeof(*R+1)); //Creating Right array
for (int i = 0; i < n1; i++) { //Fixed: i start from 0
L[i] = A[p + i];
}
// int arr_size = sizeof(A) / sizeof(A[0]);
for (int j = 0; j < n2; j++) { //Fixed: j start from 0
R[j] = A[q + j + 1];
}
L[n1] = 99; //Placing Sentinel at the end of array
R[n2] = 99;
i = 0; //Fixed: i and j to start from 0
j = 0;
/*Prior to the first iteration k = p, so the subarray is empty.
Both L[i] and R[j] are the smallest elements of their arrays and have not
been copied back to A*/
for (int k = p; k <= r; k++) { //Fixed: <=
if (L[i] <= R[j]) {
A[k] = L[i];
i++;
}
else { //Fixed: Assignment and not condition check for A[k]
A[k] = R[j];
j++;
}
}
free(L);
free(R);
}
void MERGE_SORT(int A[], int p, int r)
{
//During first iteration p = 1 & r = 8
if (p < r) {
int q = (p + r) / 2;
MERGE_SORT(A, p, q);
MERGE_SORT(A, q + 1, r);
MERGE(A, p, q, r);
}
}
/* Function to print an array */
void printArray(int Arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", Arr[i]);
printf("\n", size);
}
希望有帮助。
如有任何疑问,请回复。
关于c - 用 C 语言编写归并排序伪代码过程,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49346339/
本文实例汇总了Java各种排序算法。分享给大家供大家参考,具体如下: 1. 冒泡排序: ?
1.冒泡排序 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。 算法步
前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏。但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效。 选择排序 选择排序几乎是
我是一名优秀的程序员,十分优秀!