c - C 中的快速排序——指针和内存

Question

我是一名计算机科学新生，在指针方面我仍然遇到一些困难。我正在尝试在 C 中实现一个快速排序程序。目前有 2 个错误，但我不知道如何修复它。

1. 在主函数中，当我调用分区时，我得到了不兼容的指针类型

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;
}

Answer 1

对于初学者来说，如果数组有 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