C - 使用指针的自定义快速排序 + 比较器不起作用

Question

我正在尝试实现自定义快速排序和自定义比较器，因为我需要按两个元素对结构进行排序(如果第一个元素相等，则按第二个元素排序)。

我使用了以下代码，该代码最初发布在第一个答案中: Sorting an array using multiple sort criteria (QuickSort)

typedef struct player {
    int total;
    char name[16];
} player;

void swap(player *p1,player *p2) {
    player tmp = *p2;
    *p2 = *p1;
    *p1 = tmp;
}

int comp(const player *p1,const player *p2) {
    if (p1->total < p2->total) return 1;
    if (p1->total > p2->total) return -1;
    return strcmp(p1->name, p2->name);
}

static void quickSort(player *arr, int left, int right) {
    int m = (left+right)/2;
    int l = left, r = right;
    while (l <= r) {
        while (comp(arr+l, arr+m) < 0) l++;
        while (comp(arr+r, arr+m) > 0) r--;
        if (l <= r) {
            swap(arr+l, arr+r);
            l++; r--;
        }
    }
    if (r > left) quickSort(arr, left, r);
    if (l < right) quickSort(arr, l, right);
}

我无法让它工作。当两个总数相等时，它会成功按总计排序，但无法按名称排序。

是的，我尝试过将此比较器与标准 qsort 函数一起使用，并且效果很好。但使用它将是我最后的选择。

感谢任何帮助。

编辑:

我猜枢轴是问题所在。当我向其中添加 1 时，“名称”排序工作正常，但一些“总”元素出现乱序。

Answer 1

您的快速排序算法和标准实现之间存在许多差异(例如 http://www.codingbot.net/2013/01/quick-sort-algorithm-and-c-code.html )，主要基于边缘条件，这就是为什么当您有许多相同的条目时您能够看到问题在您的列表中进行排序。

如果将快速排序例程更改为此，一切都应该很好 - 主要区别是:

1) 主 while 循环不以相等条件继续

2)如果项目处于相同索引，则不要交换，并且交换后不要更改我们的行走指针。

3) 每次选择列表中的第一项作为枢轴，然后将其与我们走到列表中间的一项(本例中为右侧项)交换。

4)完成枢轴两侧的排序后，然后显式搜索上半部分和下半部分(即从开始到枢轴-1，然后枢轴+1到结束)。

static void quickSort(player *arr, int left, int right) {
  int m = left;
  int l = left, r = right;
  while (l < r) {
    while (comp(arr+l, arr+m) <= 0) l++;
    while (comp(arr+r, arr+m) > 0) r--;

    if (l < r) {
      swap(arr+l, arr+r);
    }
  }
  swap (arr+m, arr+r);

  if (r > left) quickSort(arr, left, r-1);
  if (l < right) quickSort(arr, r+1, right);
}