c - 如何使用快速排序对一对整数的结构进行排序？

Question

假设我有以下结构:

struct Pair {
    int x;
    int y;
}

我想按对中的第一个元素(即 x)对数组进行排序，然后按第二个元素对数组进行排序，因此如果我们给出以下内容:

input:  [(1,2), (1,0), (2,3), (1,4), (2,2)]
output: [(1,0), (1,2), (1,4), (2,2), (2,3)]

现在我有两个函数，其中一个按第一个元素对数组进行排序，第二个按第二个元素对数组进行排序，但这效率较低。如何遍历数组一次并获得所需的结果？

void sort1(Pair ps[], int size) {
    int i, j;

    for (i = 0; i < size; i++) {
        for (j = i + 1; j < size; j++) {
            if (ps[j].x > ps[j+1].x) {
                Pair temp = ps[j+1];
                ps[j+1] = ps[j];
                ps[j] = temp;
            }
        }
    }
}

void sort2(Pair ps[], int size) {
    int i, j;

    for (i = 0; i < size; i++) {
        for (j = i + 1; j < size; j++) {
            if (ps[j].y > ps[j+1].y) {
                Pair temp = ps[j+1];
                ps[j+1] = ps[j];
                ps[j] = temp;
            }
        }
    }
}

此外，是否有使用内置排序功能快速完成此操作的方法？

Answer 1

您可以使用 qsort()这是快速排序的 C 库实现。

为了使用这个函数，你需要设计一个cmp 函数来比较两个x 值，如果它们相等，则按y。

为了不把它混成一个 cmp 函数，您可以首先创建一个较小的函数来测试两个整数是否相等:

int compare_int(const int a , const int b) {
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;
    }
    return 0;
}

然后您可以将它集成到您​​的主要cmp 函数中，qsort() 将调用该函数。这个函数可以简单地是:

int cmp_func(const void *a, const void *b) {
    const pair_t *num1 = (pair_t *)a;
    const pair_t *num2 = (pair_t *)b;

    if (num1->x == num2->x) {
        return compare_int(num1->y, num2->y);
    } else if (num1->x > num2->x) {
        return +1;
    }
    return -1;
}

然后你可以像下面这样简单地调用qsort():

qsort(ps, sizeof(ps)/sizeof(ps[0]), sizeof(pair_t), cmp_func);

下面是一些执行此操作的示例代码:

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

#define ARRAYSIZE(x) ((sizeof(x))/sizeof(x[0])) 

typedef struct {
    int x;
    int y;
} pair_t;

int compare_int(const int a , const int b) {
    if ( a < b ) {
        return -1;
    } else if ( a > b ) {
        return 1;
    }
    return 0;
}

int cmp_func(const void *a, const void *b) {
    const pair_t *num1 = (pair_t *)a;
    const pair_t *num2 = (pair_t *)b;

    if (num1->x == num2->x) {
        return compare_int(num1->y, num2->y);
    } else if (num1->x > num2->x) {
        return +1;
    }
    return -1;
}

void print_array(pair_t ps[], size_t n) {
    printf("[");
    for (size_t i = 0; i < n; i++) {
        printf("(%d,%d)", ps[i].x, ps[i].y);
        if (i != n-1) {
            printf(", ");
        }
    }
    printf("]\n");
}  

int main(void) {
    pair_t ps[] = {{1,2}, {1,0}, {2,3}, {1,4}, {2,2}};

    printf("Input: ");
    print_array(ps, ARRAYSIZE(ps));

    qsort(ps, ARRAYSIZE(ps), sizeof(pair_t), cmp_func);

    printf("Output: ");
    print_array(ps, ARRAYSIZE(ps));

    return 0;
}

哪些输出:

Input: [(1,2), (1,0), (2,3), (1,4), (2,2)]
Output: [(1,0), (1,2), (1,4), (2,2), (2,3)]

注意:您的原始代码(实现冒泡排序)的平均运行时间为 O(n^2)。但是，如果您改为使用 qsort()，您将能够实现更快的平均 O(logN) 运行时间。如果 n 变大，这种差异将有助于更快地获得结果。