基于C中的布尔函数重新排序列表

Question

给定一个列表和一个布尔函数f，我如何对该列表进行重新排序，使f（element）==1的所有元素都在前面（这些元素的内部顺序无关紧要），而f（element）==0的所有元素也在列表的末尾（同样，它们的内部顺序也无关紧要）。

我试过了，但它变得很乱，有很多指针。我想知道有没有人知道一种"干净"的方法？

谢谢你的帮助。

Answer 1

如果您有一个数组，请使用qsort:

#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

这是一个与qsort兼容并使用f。的样本比较器

int comp(const void* elem1, const void* elem2) {
    int a = f(*((type*)elem1)) ? 1 : 0;
    int b = f(*((type*)elem2)) ? 1 : 0;
    return a - b;
}

如果你有一个链接列表，那么：

linkedlist* sort(linkedlist* head) {
  linkedlist* newHead = NULL;
  linkedlist* newTail = NULL;
  linkedlist* backHead = NULL;
  linkedlist* backTail = NULL;
  linkedlist* currNode = head;
  while (currNode != NULL) {
    if (f(currNode)) {
      if (newHead == NULL) {
        newHead = newTail = currNode;
      } else {
        newTail.next = currNode;
        newTail = currNode;
      }
    } else {
      if (backHead == NULL) {
        backHead = backTail = currNode;
      } else {
        backTail.next = currNode;
        backTail = currNode;
      }
    }
    currNode = currNode.next;
  }
  if (currTail != NULL) {
     currTail.next = backHead;
  }
  if (backTail != NULL) {
     backTail.next = NULL;
  }
  return currHead != NULL ? currHead : backHead;
}

Answer 2

1. 查找谓词失败的第一个节点
2. 查找传递谓词的下一个节点
3. 交换数据
4. 继续，直到第一次失败后没有节点通过谓词