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

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标识的值，继续对（子）数组进行分区。

但是，随着时间的流逝，交换值或早或晚您选择的枢轴值将改变其在数组中的位置，现在您将与枢轴索引处发生的一切进行比较。

相反，您应该保存枢轴值并进行比较。这样做还有一个好处，就是可以在内部循环中保存数组索引：

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;