线程1：EXC_BAD_ACCESS（代码= 1，地址= 0x7ffeefc00000）

Question

我是C新手，我正在学习来自coursera的算法，在这里我正在尝试实现三向快速排序，我理解我遇到了一个错误的内存错误，它发生在第一次排序数组之后。

我在这里附加我的代码和coursera讲师使用的java代码的页面，任何改变错误的建议将不胜感激。

#include <stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quicksort(int arr[],int low, int high)
{
    if(high<=low)
    return;
    int lt = low;
    int gt = high;
    int pivot = low;
    int  i = low;
    while(i<=gt)
    {
        if(arr[i]==arr[pivot])
            i++;
        else if(arr[i]<arr[pivot])
        {
            swap(&arr[i],&arr[lt]);
            i++;
            lt++;
        }
        else
        {
            swap(&arr[i],&arr[gt]);
            gt++;
        }
    }
    quicksort(arr,low,lt-1);
    quicksort(arr,gt+1,high);
}
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main()
{
    int arr[] = {5,1,2,8,7,5,5,6,5,4,5,3,9,10};
    int n = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr, 0, n-1);
    printf("Sorted array: ");
    printArray(arr,n);
    return 0;
}

而且我附上了coursera讲师的java代码Java code的图片

Answer 1

我遇到了错误的内存错误

你从Java代码中做了一个错误

    else
    {
        swap(&arr[i],&arr[gt]);
        gt++;
    }

一定是

    else
    {
        swap(&arr[i],&arr[gt]);
        gt--;
    }

在更正，编译和执行之后：

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra so.c
pi@raspberrypi:/tmp $ ./a.out
Sorted array: 1 5 2 5 3 4 5 5 5 7 6 8 9 10 

在valgrind下执行：

pi@raspberrypi:/tmp $ valgrind ./a.out
==16601== Memcheck, a memory error detector
==16601== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==16601== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==16601== Command: ./a.out
==16601== 
Sorted array: 1 5 2 5 3 4 5 5 5 7 6 8 9 10 
==16601== 
==16601== HEAP SUMMARY:
==16601==     in use at exit: 0 bytes in 0 blocks
==16601==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==16601== 
==16601== All heap blocks were freed -- no leaks are possible
==16601== 
==16601== For counts of detected and suppressed errors, rerun with: -v
==16601== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)

所以现在没有无效的内存访问...但排序不起作用，这是因为你没有遵循关于v / pivot的Java代码

你必须用int pivot = low;替换int pivot = arr[low];，当然还有arr[pivot]的其他地方pivot

之后 ：

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra so.c
pi@raspberrypi:/tmp $ ./a.out
Sorted array: 1 2 3 4 5 5 5 5 5 6 7 8 9 10 

在valgrind下：

pi@raspberrypi:/tmp $ valgrind ./a.out
==16833== Memcheck, a memory error detector
==16833== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==16833== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==16833== Command: ./a.out
==16833== 
Sorted array: 1 2 3 4 5 5 5 5 5 6 7 8 9 10 
==16833== 
==16833== HEAP SUMMARY:
==16833==     in use at exit: 0 bytes in 0 blocks
==16833==   total heap usage: 1 allocs, 1 frees, 1,024 bytes allocated
==16833== 
==16833== All heap blocks were freed -- no leaks are possible
==16833== 
==16833== For counts of detected and suppressed errors, rerun with: -v
==16833== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)