cs50 pset3排序函数

Question

已关闭。这个问题是 not reproducible or was caused by typos 。目前不接受答案。

---

这个问题是由拼写错误或无法再重现的问题引起的。虽然类似的问题可能是 on-topic在这里，这个问题的解决方式不太可能帮助 future 的读者。

已关闭 6 年前。

Improve this 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])

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