排序使用多个排序标准（快速排序）数组 [英] Sorting an array using multiple sort criteria (QuickSort)

问题描述

我试图找出如何（使用快速排序算法）来排序2审核规定的结构数组。例如说我有一个结构：

I am trying to find out how (using a quicksort algorithm) to sort an struct array by 2 criterias. For example say I had a struct of:

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函数，但我还没有如何检查丝毫的想法。这里是我的排序功能：

I am wanting to sort the elements by gender first then the IDs in ascending order. An example would be have all the males printed first with their IDs in order and then all the females with theirs. I am trying to do this without using the qsort function but I havent the slightest idea how to check . Here is my sorting function:

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但我不能找出其中的函数中包含它。

Any suggestions? I was thinking I could use strcmp but I cant figure out where to include it within the function.

推荐答案

您当然可以内联的比较函数，并为此事交换技术。这$ C $下面c是pretty基本依赖于有效的三分球，但you'l的想法。我也参加了修剪下来的快速排序，固定沿途（我希望）什么是关闭的自由。

You can certainly inline the comparison function, and a swapper for that matter. This code below is pretty basic and relies on valid pointers, but you'l get the idea. I also took the liberty of trimming down your quicksort, fixing what was off along the way (I hope).

#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

这篇关于排序使用多个排序标准（快速排序）数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！