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) 只需将索引 k 上方的元素与索引k处的当前元素。因此，外循环 (k) 需要从 0 迭代到 n - 2(比最后一个元素少一个)，并且对于每个外循环循环迭代内部循环需要从k + 1(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 answer and demo program.

<小时/>

还有一个小问题——这个测试:

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

实际上应该是:

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

这并不是不正确的(代码仍然可以工作)，但是交换相等的元素是没有意义的，所以它的效率有些低。