1

我正在尝试在 C# 中实现快速排序。我在网上找到了与下面的代码非常相似的代码：

public void Sort(List<int> list, int low, int high) 
    {
        int i = low;
        int j = high;

        IComparable pivot = list[(low + high) / 2];

        while (i <= j)
        {
            while (list[i].CompareTo(pivot) < 0)
            {
                i++;
            }
            while (list[j].CompareTo(pivot) > 0)
            {
                j--;
            }
            if (i <= j)
            {
                int temp = list[i];
                list[i++] = list[j]; // ??
                list[j--] = temp; // ??
            }
        }

        if (j > low)
        {
            Sort(list, low, j);
        }
        if (i < high)
        {
            Sort(list, i, high);
        }            
    }

代码工作正常，但我不明白为什么在交换 list[i] 和 list[j] 中的整数时需要递增和递减 i 和 j。

我是排序算法的新手。我将非常感谢任何见解..

4

1 回答 1

2

递增和递减不是针对交换本身进行的，而是为了使指针就位，以便在下一次迭代中对下一对元素进行排序。

考虑以下示例。

4    1    7    3    5    4    8    1    9
          ↑         ↑              ↑
          i       pivot            j

at 的值i大于pivot，而 at的j值小于 ，使它们有资格进行交换。但是，一旦交换准备好，重新比较相同的两个元素就没有意义了，因为我们已经知道它们在正确的位置。因此，我们进步i并j作为同一操作的一部分。

4    1    1    3    5    4    8    7    9
               ↑    ↑         ↑
               i  pivot       j

编辑：操作是后缀，这意味着它们是在分配之后完成的。以下将是等效的：

int temp = list[i];
list[i] = list[j];
i = i + 1;
list[j] = temp;
j = j + 1;
于 2013-07-11T23:27:15.200 回答