Inplace交换逻辑不适用于Quick sort，但是使用temp变量进行交换有效。为什么？

Question

在下面实现的快速排序中，我将数组的第一个元素作为枢轴。当我使用temp变量交换元素时，sort算法工作得非常好，但是当我就地交换它们时，它不起作用（将0s作为已排序数组中的元素添加）。 Kindy解释了此代码中的问题。

    public static void quickSort(int[] arr, int start, int end)
    {
        if(start < end)
        {
            int partition = partition(arr, start, end);

            quickSort(arr, start, partition-1);
            quickSort(arr, partition+1, end);
        }
    }

    public static Integer partition(int[] arr, int start, int end)
    {

        int pivot = start, i = start, j = end;

        while(i<j)
        {
            while(i<end && arr[i]<=arr[pivot])
            {
                i++;
            }

            while(arr[j]>arr[pivot])
            {
                j--;
            }

            if(i<j)
            {
                arr[i] = arr[i] + arr[j];
                arr[j] = arr[i] - arr[j];
                arr[i] = arr[i] - arr[j];   //It doesn't work

               /*int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;     
                */                          //It works


            }
        }
        arr[pivot] = arr[pivot] + arr[j];
        arr[j] = arr[pivot] - arr[j];
        arr[pivot] = arr[pivot] - arr[j];   //It doesn't work

        /*int temp = arr[pivot];
        arr[pivot] = arr[j];
        arr[j] = temp;     
        */                          //It works
        return j;
    }

Answer 1

我怀疑就地交换是问题。它工作时可能只是运气。这些行需要更改。我没有测试代码以查看是否还有其他问题

        quickSort(arr, start, partition);   // not partition - 1
                                            //  since this is Hoare partition scheme
        quickSort(arr, partition+1, end);   // this line is ok
        ...

        while(i<end && arr[i]< arr[pivot])  // not <=

Answer 2

[这种“就地交换”算法和“非就地交换”算法之间的区别在于，当pivot和j是相同的索引时，后者可以工作，而前者则不然。

如果我们想象两个索引相同，这就是您的代码：

        arr[j] = arr[j] + arr[j];
        arr[j] = arr[j] - arr[j];
        arr[j] = arr[j] - arr[j];

第二行始终将arr[j]设置为0，而不考虑其原始值，而第三行将其保留为0。