使用多個排序標準對數組進行排序（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比較器。