我的快速排序实现不起作用

Question

任何人都可以帮助我处理这段代码，因为它在执行时没有正确排序数组。我不知道出了什么问题。我使用这个结构并从文件中获取数据

typedef struct record {
    int id_field;
    char string_field[20];
    int int_field;
    double double_field;
} record;

typedef int (*CompareFunction)(void *, void *);

这是快速排序：

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

void quick_sort(void **array, int left, int right, CompareFunction compare) {
   int index;
   if (left < right) {
      index = partition(array, left, right, compare);
      quick_sort(array, left, index - 1, compare);
      quick_sort(array, index + 1, right, compare);
   }
}

int partition(void **array, int left, int right, CompareFunction compare) {
  int pivot = left + (right - left) / 2;
  int i = left;
  int j = right;
  while (i < j) {
    if (compare(array[i], array[pivot]) < 0) {
        i++;
    } else {
        if (compare(array[j], array[pivot]) > 0) {
            j--;
        } else {
            swap(&array[i], &array[j]);
            i++;
            j--;
        }
     }
  }
  swap(&array[pivot], &array[j]);

  return j;
}

这是 int 的比较函数：

int compare_int_struct(void *ptr1, void *ptr2) {
    int i1 = (*((record *) ptr1)).int_field;
    int i2 = (*((record *) ptr2)).int_field;
    if (i1 < i2) {
        return -1;
    }
    if (i1 == i2) {
        return 0;
    }
    return 1;
 }

例如：

given array    sorted array
233460      |    233460
4741192     |    1014671
1014671     |    1188961
496325      |    3119429
4476757     |    496325
3754104     |    2146160
4271997     |    2163766
4896376     |    2369159
2735414     |    3754104
2163766     |    2735414
2369159     |    4271997
1188961     |    4476757
3843159     |    4741192
2146160     |    3843159

好像是小块订货

Answer 1

问题出在你的分区例程中。

您正在选择一个主元 index，然后您通过该索引间接比较值和 l 标识的值来继续对（子）数组进行分区或 r。

但是，随着您进行交换值，您选择的枢轴值迟早会改变其在数组中的位置，您现在正在与枢轴索引处发生的任何情况进行比较。

相反，您应该保存枢轴 value 并与之进行比较。这有一个额外的好处，它可以在内部循环中保存数组索引：

int partition(void **array, int left, int right, CompareFunction compare) {
  int pivot = left + (right - left) / 2;
  int pivotValue = array[pivot];  // ********
  int i = left;
  int j = right;
  while (i < j) {
    if (compare(array[i], pivotValue) < 0) {  // ********
        i++;
    } else {
        if (compare(array[j], pivotValue) > 0) {  // ********
            j--;
        } else {
            swap(&array[i], &array[j]);
            i++;
            j--;
        }
     }
  }
  swap(&array[pivot], &array[j]);

  return j;
}

然后是最后的 swap。如果您预先选择将选定的枢轴移动到数组的开头或结尾并将该索引从剩余的分区过程中排除，那么您将使用它。有几个变体这样做，但这里 swap 只是把事情搞砸了，应该删除。

Answer 2

谢谢大家的回答。我修改了分区，现在可以使用了：

int pivot = left;
int i = left + 1;
int j = right;
while (i <= j) {
    if (compare(array[i], array[pivot]) < 0) {
        i++;
    } else {
        if (compare(array[j], array[pivot]) > 0) {
            j--;
        } else {
            swap(&array[i], &array[j]);
            i++;
            j--;
        }
    }
}
swap(&array[pivot], &array[j]);
return j;

我的快速排序实现不起作用

My quick sort implementation doesn't work

c

quicksort