c - C快速排序分段错误
问题描述
我想在 c 中编写一个快速排序代码,当我尝试运行此代码时,编译器会抱怨“分段错误(核心转储)”。我找不到问题出在哪里。有人可以帮我找到问题吗?谢谢。
#include <stdio.h>
void swap(int *m,int *n)
{
int t;
t = *m;
*m = *n;
*n = t;
}
int partition(int *a,int lo,int hi)
{
int pivot = a[hi];
int i = lo;
for(int j = lo;j < hi;j++)
{
if(a[j] < pivot)
{
//swap(&a[i],&a[j]);
int t = a[i];
a[i] = a[j];
a[j] = t;
i++;
}
}
// swap(&a[i],&a[hi]);
int t = a[hi];
a[hi] = a[i];
a[i] = t;
return i;
}
void quicksort(int *a,int lo,int hi)
{
if(lo < hi)
{
int p = partition(a,lo,hi);
quicksort(a,lo,p);
quicksort(a,p+1,hi);
}
}
int main(void)
{
int a[10] = {3,4,6,7,5,8,9,2,1,0};
quicksort(a,0,9);
for(int i = 0;i < 10;i++)
printf("%d ",a[i]);
return 0;
}
解决方案
好吧,看来您在理解快速排序方面犯了一个简单的错误。
问题是您在调用时将枢轴元素放在数组内的正确位置partition()
。
我的意思是认为最初在数组中的元素为
[ 3 , 4 , 6 , 7 , 5 , 8 , 9 , 2 , 1 , 4 ]
现在调用后partition()
,数组应该是这样的(请注意,您已选择最后一个元素作为枢轴元素,上面用粗体标记)
[ 3 , 2 , 1 , 4 , 5 , 8 , 9 , 4 , 6 , 7 ]
现在数组应该分为三部分
[ 3 , 2 , 1 ] [ 4 ] [ 5 , 8 , 9 , 4 , 6 , 7 ]
我们知道枢轴元素在正确的位置,所以不需要触摸中间部分,只需继续剩余的左右部分。
你所做的只是之后的两部分partition()
[ 3 , 2 , 1 , 4 ] [ 5 , 8 , 9 , 4 , 6 , 7 ]
现在对于 [ 3 , 2 , 1 , 4 ] ,当您调用 时quicksort()
,它将陷入无限递归。
我已经修改了下面的部分,希望对您有所帮助
void quicksort(int *a,int lo,int hi)
{
if(lo < hi)
{
int p = partition(a,lo,hi);
quicksort(a,lo,p-1);
quicksort(a,p+1,hi);
}
}
推荐阅读
- sql - 我可以将 table1 的每一行加入到 table 2 的唯一行吗?
- c - 如何解决遍历森林中抛出的异常
- android - 如何在flutter中使用Dio将flutter_sound包录制的音频上传到服务器?
- constraints - 如何限制 GAMS 混合整数非线性规划中非零变量的数量?
- python-3.x - 如何将 Shaka 打包器与 python 子进程调用一起使用?我收到此错误无效的流描述符名称/值对:
- angular - Ionic 3 /Angular 下拉从嵌套数组对象中选择值
- reporting-services - SSRS - 如何仅在分组表拆分时设置分页符?
- shopify - 标记过滤器到 Shopify
- node.js - 如何按照我调用的顺序依次执行 fs 函数
- nuget - 如何安装 nuget 包 teamcity cloud?