使用多个排序标准对数组进行排序（QuickSort）

Question

我想了解如何（使用快速排序算法）按2个标准对结构数组进行排序。例如说我有一个结构：

struct employee{ 
    char gender[12]; 
    char name[12]; 
    int id; 
}; 

说我的输入为：

struct employee arr[3]= 
{ 
    {"male","Matt",1234}, 
    {"female","Jessica",2345}, 
    {"male","Josh",1235} 
}; 

我想按性别升序排列元素第一则的ID进行排序。一个例子就是让所有的男性先打印他们的ID，然后再打印所有的女性。我试图做到这一点，而不使用qsort函数，但我没有丝毫的想法如何检查。这里是我的排序功能：

void quicksort(struct employee *arr, int left, int right) 
{ 
    int pivot, l, r, temp; 
    if(left < right) 
    { 
     p = left; 
     l = left; 
     r = right; 
     while(l < r) 
     { 

      while(arr[l].id <= arr[p].id && l <= right) 
       l++; 
      while(arr[r].id > arr[p].id && r >= left) 
       r--; 

      if(l < r) 
      { 
       temp = arr[l].id; 
       arr[l].id = arr[r].id; 
       arr[r].id = temp; 
      } 
     } 


     temp = arr[r].id; 
     arr[r].id = arr[p].id; 
     arr[p].id = temp; 

     quicksort(arr, left, r-1); 
     quicksort(arr, r+1, right); 
    } 
} 

有什么建议吗？我在想我可以使用strcmp，但我无法弄清楚它在函数中的位置。

Answer 1

你当然可以内联比较函数，并为此提供一个交换器。下面的这段代码非常基本，依赖于有效的指针，但是你明白了。我也随意修改你的快速排序，修正了一路上的情况（我希望）。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

// employee record 
struct employee 
{ 
    char gender[12]; 
    char name[12]; 
    int id; 
}; 

// swap employee records 
void swap_employee(struct employee *left, struct employee *right) 
{ 
    struct employee tmp = *right; 
    *right = *left; 
    *left = tmp; 
} 

// compare employee records 
int compare_employee(const struct employee* left, 
        const struct employee* right) 
{ 
    int gender = strcmp(left->gender, right->gender); 
    return (gender ? gender : (left->id - right->id)); 
} 

// quicksort for employees 
static void quicksort_(struct employee *arr, int left, int right) 
{ 
    struct employee p = arr[(left+right)/2]; // as good as any 
    int l = left, r = right; // movable indicies 

    while (l <= r) 
    { 
     while (compare_employee(arr+l, &p) < 0) 
      ++l; 
     while (compare_employee(arr+r, &p) > 0) 
      --r; 
     if (l <= r) 
     { 
      swap_employee(arr+l, arr+r); 
      ++l; --r; 
     } 
    } 

    if (left < r) 
     quicksort_(arr, left, r); 
    if (l < right) 
     quicksort_(arr, l, right); 
} 

// exposed API 
void quicksort(struct employee *arr, int count) 
{ 
    if (arr && (count>0)) 
     quicksort_(arr, 0, count-1); 
} 

/* sample usage */ 
int main(int argc, char *argv[]) 
{ 
    struct employee arr[]= 
    { 
     {"male","Matt",1234}, 
     {"female","Jessica",2345}, 
     {"male","Josh",1235}, 
     {"female","Betsy",2344}, 
     {"male","Roger",1233} 
    }; 

    quicksort(arr, sizeof(arr)/sizeof(arr[0])); 

    for (int i=0;i<sizeof(arr)/sizeof(arr[0]);++i) 
     printf("%s, %s, %d\n", arr[i].gender,arr[i].name, arr[i].id); 

    return EXIT_SUCCESS; 
} 

结果

female, Betsy, 2344 
female, Jessica, 2345 
male, Roger, 1233 
male, Matt, 1234 
male, Josh, 1235 

Answer 2

只要使用内置的qsort，并传递一个比较函数，先比较性别，并在第一次比较中仅在“关系”的情况下查询ID号。

Answer 3

我想你应该按照性别先排序你的数组，一个是男性，一个是女性。然后使用quicksort函数在这两个数组中进行排序。

您可以使用strcmp将原始数组排序为两个数组：一个是男性，一个是女性。

Answer 4

这并不难。你只需要一个函数（或代码块看你想要它“硬编码”）来比较你的结构。在你给出的示例代码中，使用arr[l].id <= arr[p].id来比较当前对象。那就是你只是在考虑编制你的元素适合的地方。在这一点上，您只需要使用其他字段进行比较。用一个函数会更加整齐（在你之前的问题中，我给了你一个这样的函数）。

您也只在交换时移动ID字段 - 在数据项中保留名称和性别不变。你应该移动整个结构。

Answer 5

int compare_employee (struct employee * a, struct employee * b) { 
    int diff = strcmp(a->gender, b->gender); 

    if (diff) // if gender different 
     return -diff; // sort descending, please double check this and reverse in case I am wrong 

    return a->id - b->id; // else sort by id 
} 

将输出一个负数如果a < b，正如果a > b，零，如果它们是相等的。

在您自己的快速排列中使用它或作为qsort比较器。