c - C 中使用 char 数组进行快速排序

Question

我正在尝试在 C 中实现快速排序，对 char 数组进行排序。我正在使用也可以在维基百科上找到的递归方法。这是相关代码:

#define TSIZE 32
#define TNUM 100000

交换宏:

#define SWAP(a, b, size)                    \
  do                                        \
    {                                       \
      size_t __size = (size);               \
      char *__a = (a), *__b = (b);          \
      do                                    \
      {                                     \
        char __tmp = *__a;                  \
        *__a++ = *__b;                      \
        *__b++ = __tmp;                     \
      } while (--__size > 0);               \
  } while (0)

这个交换宏取自已经在 C 中实现的 qsort 函数。

字符数组:

char TWEETS[TNUM * TSIZE];

我省略了将所有数据读入 char 数组的部分，因为我这里的设置与 qsort() 函数完美配合。然而，这里是正在读取的数据的摘录:

0 0 Feb 09 @RafinhaCosgrove OIE VOLTEI <33
0 1 Feb 19 @Nha_RDO tanyak ajah , taik idup dia!
0 2 Mar 08 @w0nderlxss No Hi's Mine

最初的快速排序调用:

quicksort(TWEETS, 0, TNUM-1, compare);

比较函数:

int compare(const void* ptr1, const void* ptr2) {
    int i;
    unsigned char * t1 = (unsigned char *) ptr1;
    unsigned char * t2 = (unsigned char *) ptr2;
    for (i = 6; i < TSIZE; i++) {
        if (t1[i] > t2[i])
            return -1;
        if (t2[i] > t1[i])
            return 1;
    }
    return 0;
}

快速排序函数:

void quicksort(void* base, int left, int right, int (*compar)(const void* , const void*))
{
    if(left < right) {
        int pivot = partition(base, left, right, compar);
        quicksort(base, left, pivot-1, compar);
        quicksort(base, pivot+1, right, compar);
    }
}

最后是分区函数:

int partition(void* arr, int left, int right, int (*compar)(const void* , const void*))
{
    char* cArr = (char*) arr;

    int i;
    int pivotIndex = (left+right)/2;
    char* pivotValue = &cArr[TSIZE * pivotIndex];
    int index = left;

    SWAP(&cArr[TSIZE * pivotIndex], &cArr[TSIZE * right], TSIZE);

    for(i = left; i < right; i++) {
        if(compar((void*) &cArr[TSIZE * i], (void*) pivotValue) < 0) {
            SWAP(&cArr[TSIZE * i], &cArr[TSIZE * index], TSIZE);
            index++;
        }
    }
    SWAP(&cArr[TSIZE * index], &cArr[TSIZE * right], TSIZE);
    return index;
}

现在有几件事你应该知道:
1) 当使用 int 数组和几个数字而不是 char 数组进行排序时，代码设置有效。
2) 代码设置(读取数据等)仅在使用 qsort() 函数时有效。我还将此结果用作我自己实现的输出的比较。
3) 既然和qsort()一起工作，比较函数应该不会出错。
4) 由于它与 qsort() 一起工作，并且交换宏取自 qsort() 实现，它也不应该有问题。

为了完整起见，这里是使用 int 数组而不是 char 数组(再次有效)时的相关代码部分。

调用主函数:

int array[15] = {9, 6, 2, 0, 3, 1, 4, 8, 5, 7, 7, 50, 132, 12, 45};
quicksort(array, 0, 14, compare);

交换和分区功能:

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int* arr, int left, int right, int (*compar)(const void* , const void*))
{
    int i;
    int pivotIndex = (left+right)/2;
    int pivotValue = arr[pivotIndex];
    int index = left;

    swap(&arr[pivotIndex], &arr[right]);

    for(i = left; i < right; i++) {
        if(arr[i] < pivotValue) {
            swap(&arr[i], &arr[index]);
            index++;
        }
    }
    swap(&arr[index], &arr[right]);
    return index;
}

如您所见，我在这里完全不知所措。非常感谢任何帮助。

Answer 1

在partition()中，改变

char* pivotValue = &cArr[TSIZE * pivotIndex];

到

char* pivotValue = &cArr[TSIZE * right];

自从之后

SWAP(&cArr[TSIZE * pivotIndex], &cArr[TSIZE * right], TSIZE);

枢轴元素位于右侧，不再位于pivotIndex。

并且您的算法正在向后排序。如果这不是您想要的，请更改 compare() 的符号。