我是一名计算机科学新生,在指针方面我仍然遇到一些困难。我正在尝试在 C 中实现一个快速排序程序。目前有 2 个错误,但我不知道如何修复它。
在主函数中,当我调用分区时,我得到了不兼容的指针类型
在交换函数上:线程1:EXC_BAD_ACCESS(code=1,address=0x200000007)
void swap(int *i, int* j){
*i = *j;
*j = *i;
*i = *j;
}
void partition(int* array[], int size){
int pivot = size;
int i = - 1;
for(int j = 0 ; j < size - 1 ; j++){
if(array[j] < array[pivot]){
i++;
swap(array[i],array[j]);
}
}
}
int main() {
int array[] = {7,2,1,8,6,3,5,4};
int size = sizeof(array)/sizeof(array[0]);
partition(&array,size);
return 0;
}
最佳答案
对于初学者来说,如果数组有 N 个元素,则索引的有效范围为 [0, N-1]
因此尝试访问数组之外的内存
int pivot = size;
int i = - 1;
for(int j = 0 ; j < size - 1 ; j++){
if(array[j] < array[pivot])
^^^^^^^
你的函数交换没有意义。
void swap(int *i, int* j){
*i = *j;
*j = *i;
*i = *j;
}
第一个表达式语句之后
*i = *j;
指针i
和j
指向的两个对象将具有相同的值。
该函数可以通过以下方式定义。
void swap( int *p, int *q )
{
int tmp = *p;
*p = *q;
*q = tmp;
}
并称其为
swap( &array[i], &array[j] );
功能分区也无效。除了使用的算法不正确之外,至少其第一个参数的声明也不正确。
而不是
void partition( int* array[], int size );
函数应该这样声明
void partition( int *array, int size );
或更准确地说,例如
void partition( int *array, size_t size );
该函数应该这样调用
int array[] = {7,2,1,8,6,3,5,4};
size_t size = sizeof(array)/sizeof(array[0]);
partition( array,size );
另一方面,函数partition
应该返回将数组分为两部分的位置。所以最终的函数声明将如下所示
size_t partition( int array[], size_t size );
下面有一个演示程序,展示了如何使用函数 swap
和 partition
编写递归函数快速排序。
#include <stdio.h>
void swap( int *p, int *q )
{
int tmp = *p;
*p = *q;
*q = tmp;
}
size_t partition( int a[], size_t n, int pivot )
{
size_t i = 0;
while ( i != n )
{
while ( i != n && a[i] < pivot ) i++;
while ( i != n && !( a[--n] < pivot ) );
if ( i != n ) swap( a + i, a + n );
}
return i;
}
void quick_sort( int a[], size_t n )
{
if ( n != 0 )
{
size_t pos = partition( a, n - 1, a[n - 1] );
swap( a + pos, a + n - 1 );
quick_sort( a, pos );
quick_sort( a + pos + 1, n - pos - 1 );
}
}
int main(void)
{
int a[] = { 7, 2, 1, 8, 6, 3, 5, 4 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ )
{
printf( "%d ", a[i] );
}
putchar( '\n' );
quick_sort( a, N );
for ( size_t i = 0; i < N; i++ )
{
printf( "%d ", a[i] );
}
putchar( '\n' );
return 0;
}
程序输出为
7 2 1 8 6 3 5 4
1 2 3 4 5 6 7 8
关于c - C 中的快速排序——指针和内存,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56724611/