cs50 pset3 排序函数

Question

我在 pset3 上实现排序功能时遇到问题。我使用了 GDB，发现我的排序函数没有对任何东西进行排序。我不确定是否存在语法问题，或者逻辑是否有点搞砸了。

void sort(int values[], int n)
{
    for (int k = 0; k < n; k++)
    {
        for (int j = 0; j < n; j++)
        {
            if (values[k] >= values[j])
            {
                 int temp = values[k];
                 values[k] = values[j];
                 values[j] = temp;
            }
        }
    }
}

Answer 1

你很接近，但你的循环不太正确 - 更改：

for (int k = 0; k < n; k++)
{
    for (int j = 0; j < n; j++)
    {

至：

for (int k = 0; k < n - 1; k++)
{
    for (int j = k + 1; j < n; j++)
    {

要理解为什么需要进行此更改，请考虑内循环 (j) 只需将元素 above 与索引 k 进行比较索引 k 处的当前元素。所以外循环（k）需要从0迭代到n - 2（比最后一个元素少一个），并且对于每个外循环迭代，内循环需要从[=迭代20=]（k 上方的第一个元素）到 n - 1（最后一个元素）。

NOTE: by pure chance it seems that the original code does appear to work correctly, even though it appears at first glance that it shouldn't. I have tested it with various edge cases and even though it performs many redundant swaps, the final result always seems to be sorted (suprisingly though the output is in descending order whereas the fixed code generates results in ascending order, as expected). Credit to Jonathan Leffler for spotting this - see his .

另外一个小问题——本次测试：

        if (values[k] >= values[j])

真的应该是：

        if (values[k] > values[j])

它本身并没有错（代码仍然有效），但是交换相等的元素没有意义，所以写起来效率有点低。

Answer 2

我把你的代码转换成了一个完整的程序。它比 MCVE 更大，因为它具有用于改组数组和打印结果的支持代码，当然还有用于执行这些操作的 main()。

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

static int rand_int(int n)
{
    int limit = RAND_MAX - RAND_MAX % n;
    int rnd;

    while ((rnd = rand()) >= limit)
        ;
    return rnd % n;
}

static void shuffle(int *array, int n)
{
    for (int i = n - 1; i > 0; i--)
    {
        int j = rand_int(i + 1);
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }
}

static void print_array(int n, int a[n])
{
    for (int i = 0; i < n; i++)
        printf(" %d", a[i]);
    putchar('\n');
}

static void sort(int values[], int n)
{
    for (int k = 0; k < n; k++)
    {
        for (int j = 0; j < n; j++)
        {
            if (values[k] >= values[j])
            {
                 int temp = values[k];
                 values[k] = values[j];
                 values[j] = temp;
            }
        }
    }
}

int main(int argc, char **argv)
{
    if (argc > 1)
    {
        long l = strtol(argv[1], 0, 0);
        unsigned u = (unsigned)l;
        printf("Seed: %u\n", u);
        srand(u);
    }

    int data3[3] = { 3, 1, 2 };
    print_array(3, data3);
    sort(data3, 3);
    print_array(3, data3);

    int data5[5] = { 0, 2, 6, 1, 5, };
    for (int i = 0; i < 5; i++)
    {
        shuffle(data5, 5);
        print_array(5, data5);
        sort(data5, 5);
        print_array(5, data5);
    }

    int data9[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    for (int i = 0; i < 9; i++)
    {
        shuffle(data9, 9);
        print_array(9, data9);
        sort(data9, 9);
        print_array(9, data9);
    }

    return 0;
}

随机播放代码实现了 Fisher-Yates shuffle，并且是基于来自 answer by Roland Illig 的代码。如果在没有种子参数的情况下调用，它每次都会生成相同的输出。

代码在 macOS Sierra 10.12.1 和 GCC 6.2.0 上编译和测试。

示例输出：

Seed: 123456789
 3 1 2
 3 2 1
 6 0 1 5 2
 6 5 2 1 0
 0 6 1 2 5
 6 5 2 1 0
 0 1 2 6 5
 6 5 2 1 0
 5 0 6 1 2
 6 5 2 1 0
 1 6 5 2 0
 6 5 2 1 0
 0 4 8 3 7 5 1 6 2
 8 7 6 5 4 3 2 1 0
 7 4 0 5 6 8 3 2 1
 8 7 6 5 4 3 2 1 0
 1 2 7 5 0 8 3 6 4
 8 7 6 5 4 3 2 1 0
 3 8 7 5 2 1 0 6 4
 8 7 6 5 4 3 2 1 0
 1 4 2 6 3 0 7 5 8
 8 7 6 5 4 3 2 1 0
 2 3 7 4 8 0 5 6 1
 8 7 6 5 4 3 2 1 0
 3 4 5 8 6 2 0 7 1
 8 7 6 5 4 3 2 1 0
 3 6 7 4 8 2 5 1 0
 8 7 6 5 4 3 2 1 0
 0 8 7 3 4 6 5 1 2
 8 7 6 5 4 3 2 1 0

这显示数据每次都按降序排序，尽管随机输入不同。

cs50 pset3 排序函数

cs50 pset3 sort function

c

cs50